Most efficient way to flatten a nested Dictionary?

Question

The catch is to build the Key string as if it were a namespace. Doing this with recursion is my current implementation, but I'm sure there are more stack-friendly options (LINQ? Iterative?) which I have not yet been able to find. Almost every example is too simple and does not take into account the ability to "namespace" them based on key hierarchy.

Here is a quick example of the layout of my dictionary. Hopefully this is easy enough to understand - I wanted to be thorough.

I convert JSON similar to this (nested, to save data over the wire):

"entity": {
    "foo": {
      "bar": {
        "baz": {
          "2": "description",
          "1": "title"
             }
          }

Into a Dictionary<string,object>. When Value is string, that's the end of the "namespace". A detailed, confusing look at this object:

[0] {[entity, Dictionary[String,Object]]}   KeyValuePair<string,object>
  Key   "entity"    string
  Value Count = 1   object {Dictionary<string,object>}
    [0] {[foo, Dictionary[String,Object]]}  KeyValuePair<string,object>
    Key "foo"   string
      Value Count = 12  object {Dictionary<string,object>}
      [0]   {[bar, Dictionary[String,Object]]}  KeyValuePair<string,object>
        Key "bar"   string
        Value   Count = 1   object {Dictionary<string,object>}
          [0]   {[baz, Dictionary[String,Object]]}  KeyValuePair<string,object>
          Key   "baz"   string
          Value Count = 3   object {Dictionary<string,object>}
            [0] {[3, title]}    KeyValuePair<string,object>
              Key   "3" string
              Value "title" object {string}

This KeyValuePair would end up being: "entity.foo.bar.baz.title.3", "3"

why don't you store "entity.foo.bar.baz.title" as key inside one dictionary? If this is not possible could you provide a query example, how you would query your hierarchy. — duedl0r
– duedl0r, Commented Mar 27, 2013 at 15:53
@duedl0r It's nested because the library of keys is very large and is being sent in the form of JSON. Nesting vastly reduces the amount of data to transfer. — erodewald
– erodewald, Commented Mar 27, 2013 at 15:55
@CuongLe I'll try to think of a better way to display the layout. This is just a simple concatenation of all parent keys, if I knew how to achieve that in LINQ I would post the code... — erodewald
– erodewald, Commented Mar 27, 2013 at 15:56
@erode: I don't understand why you would make sending data and representing data in memory dependent. You obviously wanted to simplify your data transfer stuff, with the cost of having a strange data structure. Maybe you have to rethink your data transfer.. — duedl0r
– duedl0r, Commented Mar 27, 2013 at 16:03

Nicholas Carey · Accepted Answer · 2013-03-27 17:32:21Z

It's just a simple treewalk. The recursive implementation should look something like this:

static void Main( string[] args )
{
  Dictionary<string,object> nested = LoadNestedDictionary() ;
  Dictionary<string,string> flat   = new Dictionary<string, string>() ;
  Flatten(nested,flat) ;
  return;
}

/// <summary>
/// The wrapper method. Invoke this from your code
/// </summary>
/// <param name="input"></param>
/// <param name="output"></param>
private static void Flatten( IEnumerable<KeyValuePair<string,object>> input , Dictionary<string,string> output )
{
  foreach ( KeyValuePair<string,object> item in input )
  {
    string key   = item.Key   ;
    object value = item.Value ;
    if ( value is string )
    {
      output.Add(key,(string)value) ;
    }
    else if ( value is Dictionary<string,object> )
    {
      Flatten( key , (IEnumerable<KeyValuePair<string,object>>) value , output ) ;
    }
    else
    {
      throw new InvalidOperationException();
    }
  }
  return ;
}

/// <summary>
/// The core method. Called only from the wrapper method
/// </summary>
/// <param name="root"></param>
/// <param name="input"></param>
/// <param name="output"></param>
private static void Flatten( string root , IEnumerable<KeyValuePair<string,object>> input , Dictionary<string,string> output )
{
  foreach ( KeyValuePair<string,object> item in input )
  {
    string segment = item.Key ;
    string key     = root + "." + segment ;
    object value   = item.Value ;
    if ( value is string )
    {
      string s = (string) value ;
      output.Add(key,s) ;
    }
    else if ( value is Dictionary<string,object> )
    {
      Dictionary<string,object> d = (Dictionary<string,object>) value ;
      Flatten(key,d,output);
    }
    else
    {
      throw new InvalidOperationException();
    }
  }
  return ;
}

Correct, I already use recursion. I'm curious if there is a simpler, cleaner, or more efficient way to do this. My first thought was LINQ's SelectMany<T> but I am not sure it is possible to do the key namespacing with that method.
SelectMany() flattens a collection of collections. It doesn't know how to walk arbitrarily deep. You can replace the recursion with a stack, but you've still got to walk a tree of arbitrary depth and build your composite key as you descend it. I've added an alternative, more "LINQY" solution, though.

Collectives™ on Stack Overflow

Most efficient way to flatten a nested Dictionary?

1 Answer 1

2 Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Related