Databases
StackOverflow2013
Postsdbo
PODoes iterating with foreach loop over a dictionary require normal hashtable accesses?
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PODoes iterating with foreach loop over a dictionary require normal hashtable accesses?
    text
    copied!<p>I am writing an application that is primarily performance intensive. After writing a quick benchmark today I have found that dictionary access time is significantly slower than array access time (up to a 100 times), though both are O(1). I tried finding similar results on the internet, but to no avail. Does this seem right? It makes sense to me as there is hashing involved for the dictionary, and not for the array.</p> <p>I am now weighing up the pros and cons of the dictionary, and considering if I should attempt a faster implementation. In at least 3 instances of my application I loop through all my dictionaries (there are quite a few) with a foreach loop. So now to get to my question, does the foreach loop have to go through the "slow" (I speak relatively here) hashing process, or does it simply maintain an internal list that it can quickly iterate over? If this is the case, I'd be more likely to stick with the dictionary.</p> <p>For some extra info, the application is a simple 2D game, and the dictionary is to store in game entities. There really are very many though. And yes, I already have a working solution. This is post-optimization, not pre.</p> <p>Here is the benchmark I wrote. It may be very wrong, as I'm no expert in the field:</p> <pre><code> public static int dict(Dictionary&lt;key,int&gt; dict, key k) { int i; //dict.TryGetValue(k,out i); i = dict[k]; //both these version yield the same results return i; } public static int arr(int[,] arr, key k) { int i; i = arr[k.x, k.y]; return i; } public struct key { public int x, y; public key (int x, int y){ this.x = x; this.y = y; } } public static void Main() { int dim = 256; Dictionary&lt;key,int&gt; dictVar = new Dictionary&lt;key,int&gt;(dim*dim*10); int[,] arrVar = new int[dim,dim]; for (int i = 0; i &lt; dim; ++i) { for (int j = 0; j &lt; dim; ++j) { arrVar[i, j] = i + j * i; dictVar.Add(new key(i, j), i + i * j); } } const int iterations = 1000000; key k = new key(200, 200); TestTime(dict, dictVar, k, iterations); TestTime(arr, arrVar, k, iterations); } public static void TestTime&lt;T1, T2, TR&gt;(Func&lt;T1, T2, TR&gt; action, T1 obj1, T2 obj2, int iterations) { Stopwatch stopwatch = Stopwatch.StartNew(); for (int i = 0; i &lt; iterations; ++i) action(obj1, obj2); Console.WriteLine(action.Method.Name + " took " + stopwatch.Elapsed); } </code></pre>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload