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 Теги: ,,

1 comment:

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