Iterate over a nested dictionary

Question

I'm trying to iterate through the following nested dictionary instance:

Dictionary<String, Dictionary<Datetime, int>> nestedDictionary =
    new Dictionary<String, Dictionary<Datetime, int>>()

The goal is to iterate through all integers in the dictionary. To iterate over the dictionary instance I use a nested foreach loop, as shown below:

int highestTargetInConstraint = 0;
foreach(String key1 in nestedDictionary.Keys) 
{
    foreach(int targetValue in nestedDictionary[key1].Values) 
    {
        if(targetValue > 5) { continue; }

        if(targetValue > highestTargetInConstraint)
        {
            highestTargetInConstraint = targetValue;
        }
    }
}

This is the most appropriate way to loop through a flat dictionary as mentioned in this post. I can't imagine to get faster than this, but maybe you can refute.

Now I'm wondering if there is a syntactically better way to loop through a nested dictionary by using a custom iterator. Useful hints and pointers to relevant documents are appreciated.

Answer 1

It is more efficient to iterate through the values directly rather than iterating through the keys and then doing an extra lookup (as in your sample code).

So this is better:

foreach (var dictionary in nestedDictionary.Values)
{
    foreach (int targetValue in dictionary.Values)
    {
        // Do something with targetValue
    }
}

Here's some test code to compare the speed with the OP:

using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace FooBar
{
    class Program
    {
        static void Main(string[] args)
        {
            var nestedDictionary = new Dictionary<String, Dictionary<DateTime, int>>();

            int numInnerDictionaries = 5000;
            int numInnerInts         = 5000;

            for (int i = 0; i < numInnerDictionaries; ++i)
            {
                var innerDict = new Dictionary<DateTime, int>();

                var start = new DateTime(2020, 01, 01);

                for (int j = 0; j < numInnerInts; ++j)
                    innerDict.Add(start.AddSeconds(j), j);

                nestedDictionary.Add(i.ToString(), innerDict);
            }

            var sw = new Stopwatch();

            for (int trial = 0; trial < 5; ++trial)
            {
                sw.Restart();
                method1(nestedDictionary);
                sw.Stop();
                Console.WriteLine("method1() took " + sw.Elapsed);
                double method1Ticks = sw.ElapsedTicks;

                sw.Restart();
                method2(nestedDictionary);
                sw.Stop();
                Console.WriteLine("method2() took " + sw.Elapsed);
                Console.WriteLine($"method1() was {method1Ticks/sw.ElapsedTicks} times faster.");

                Console.WriteLine();
            }
        }

        static long method1(Dictionary<String, Dictionary<DateTime, int>> nestedDictionary)
        {
            long total = 0;

            foreach (var dictionary in nestedDictionary)
            {
                foreach (var item in dictionary.Value)
                {
                    total += item.Value;
                }
            }

            return total;
        }

        static long method2(Dictionary<String, Dictionary<DateTime, int>> nestedDictionary)
        {
            long result = 0;

            foreach(String key1 in nestedDictionary.Keys)
            {
                foreach(int targetValue in nestedDictionary[key1].Values)
                {
                    result += targetValue;
                }
            }

            return result;
        }
    }
}

When I run a RELEASE (not DEBUG) build, it reports that the improved method is just over 3 times faster than the original method. A 3x speedup isn't too bad...

Of course, how much it is speeded up depends on how many outer dictionaries there are - the more there are, the more the speedup.

For example, if I change numInnerDictionaries to 50 the speedup is only around twice as fast.

Answer 2

Here it is in LINQ. Only one line to actually do it - the rest is setup and display.

// Set up some data
var in1 = new Dictionary<DateTime, int> { { DateTime.Now, 1 }, { DateTime.Now, 2 }, { DateTime.Now, 3 } };
var in2 = new Dictionary<DateTime, int> { { DateTime.Now, 11 }, { DateTime.Now, 12 }, { DateTime.Now, 13 } };
var in3 = new Dictionary<DateTime, int> { { DateTime.Now, 21 }, { DateTime.Now, 22 }, { DateTime.Now, 23 } };

Dictionary<string, Dictionary<DateTime, int>> nestedDictionary = new Dictionary<string, Dictionary<DateTime, int>>
{
    { "A",in1 },
    { "B",in2 },
    { "C",in3 }
};

// Do the query
 IEnumerable<int> ints = nestedDictionary.SelectMany(n => n.Value.Select(s => s.Value));

// Show the results
foreach (int i in ints)
    Console.WriteLine(i);