Wednesday, February 24, 2010

C# - the fastest way to iterate over dictionary

Having a big dictionary, say 1M of <double,double> samples – what is the fastest way to iterate over it?
Comparing 3 options (iterate over KeyValuePair in the dictionary, iterate over Values collection and iterate over Keys collection) – below is code and timing comparison results.
// Of course if you iterating over Keys collection and accessing the value by key – it would be the slowest case.

// Create sample dictionary
var random = new Random();
var randomDictionaryOfDoubles =
    Enumerable.Repeat(0, 1000000).Select(
        i => Convert.ToDouble(random.Next()))
        .Distinct().OrderBy(i=>i)
        .ToDictionary(i => i);
double total = 0.0;
var stopWatch = new Stopwatch();
//Console.WriteLine("Starting KVP");
stopWatch.Reset();
stopWatch.Start();
foreach (KeyValuePair<double, double> kvp in randomDictionaryOfDoubles)
{
    total += (kvp.Value);
}
stopWatch.Stop();
Console.WriteLine("KVP took:    {0} Total = {1}", stopWatch.Elapsed, total);
//Console.WriteLine("Starting Values");
total = 0.0;
stopWatch.Reset();
stopWatch.Start();
// To get the values alone, use the Values property.
Dictionary<double, double>.ValueCollection valueColl = randomDictionaryOfDoubles.Values;
foreach (double d in valueColl)
{
    total += d;
}
stopWatch.Stop();
Console.WriteLine("Values took: {0} Total = {1}", stopWatch.Elapsed, total);
//Console.WriteLine("Starting keys");
total = 0.0;
stopWatch.Reset();
stopWatch.Start();
// To get the keys alone, use the Keys property.
Dictionary<double, double>.KeyCollection keyColl = randomDictionaryOfDoubles.Keys;
foreach (double d in keyColl)
{
    total += d;
}
stopWatch.Stop();
Console.WriteLine("Keys took:   {0} Total = {1}", stopWatch.Elapsed, total);
Console.ReadLine();

Here are results:

Method Time spent in iteration
Over key-value pairs 00:00:00.1854684
Over Values collection 00:00:00.1221380
Over Keys collection 00:00:00.0955291

Related article: http://dotnetperls.com/dictionary-lookup

Technorati Теги: ,,

5 comments:

Anonymous said...
This comment has been removed by a blog administrator.
Leo said...

Given that in both KeyValues and Values you have the value available, would be good to include the retrieval of the value on the key iteration.

Leo said...

Given that in both KeyValues and Values you have the value available, would be good to include the retrieval of the value on the key iteration.

Leo said...

Given that in both KeyValues and Values you have the value available, would be good to include the retrieval of the value on the key iteration.

Leo said...

Given that in both KeyValues and Values you have the value available, would be good to include the retrieval of the value on the key iteration.