StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>For very small collections the difference is going to be negligible. At the low end of your range (500k items) you will start to see a difference if you're doing lots of lookups. A binary search is going to be O(log n), whereas a hash lookup will be O(1), <a href="https://stackoverflow.com/questions/200384/constant-amortized-time">amortized</a>. That's not the same as truly constant, but you would still have to have a pretty terrible hash function to get worse performance than a binary search.</p> <p>(When I say "terrible hash", I mean something like:</p> <pre><code>hashCode() { return 0; } </code></pre> <p>Yeah, it's blazing fast itself, but causes your hash map to become a linked list.)</p> <p><a href="https://stackoverflow.com/a/28566419/1288">ialiashkevich</a> wrote some C# code using an array and a Dictionary to compare the two methods, but it used Long values for keys. I wanted to test something that would actually execute a hash function during the lookup, so I modified that code. I changed it to use String values, and I refactored the populate and lookup sections into their own methods so it's easier to see in a profiler. I also left in the code that used Long values, just as a point of comparison. Finally, I got rid of the custom binary search function and used the one in the <code>Array</code> class.</p> <p>Here's that code:</p> <pre><code>class Program { private const long capacity = 10_000_000; private static void Main(string[] args) { testLongValues(); Console.WriteLine(); testStringValues(); Console.ReadLine(); } private static void testStringValues() { Dictionary<String, String> dict = new Dictionary<String, String>(); String[] arr = new String[capacity]; Stopwatch stopwatch = new Stopwatch(); Console.WriteLine("" + capacity + " String values..."); stopwatch.Start(); populateStringArray(arr); stopwatch.Stop(); Console.WriteLine("Populate String Array: " + stopwatch.ElapsedMilliseconds); stopwatch.Reset(); stopwatch.Start(); populateStringDictionary(dict, arr); stopwatch.Stop(); Console.WriteLine("Populate String Dictionary: " + stopwatch.ElapsedMilliseconds); stopwatch.Reset(); stopwatch.Start(); Array.Sort(arr); stopwatch.Stop(); Console.WriteLine("Sort String Array: " + stopwatch.ElapsedMilliseconds); stopwatch.Reset(); stopwatch.Start(); searchStringDictionary(dict, arr); stopwatch.Stop(); Console.WriteLine("Search String Dictionary: " + stopwatch.ElapsedMilliseconds); stopwatch.Reset(); stopwatch.Start(); searchStringArray(arr); stopwatch.Stop(); Console.WriteLine("Search String Array: " + stopwatch.ElapsedMilliseconds); } /* Populate an array with random values. */ private static void populateStringArray(String[] arr) { for (long i = 0; i < capacity; i++) { arr[i] = generateRandomString(20) + i; // concatenate i to guarantee uniqueness } } /* Populate a dictionary with values from an array. */ private static void populateStringDictionary(Dictionary<String, String> dict, String[] arr) { for (long i = 0; i < capacity; i++) { dict.Add(arr[i], arr[i]); } } /* Search a Dictionary for each value in an array. */ private static void searchStringDictionary(Dictionary<String, String> dict, String[] arr) { for (long i = 0; i < capacity; i++) { String value = dict[arr[i]]; } } /* Do a binary search for each value in an array. */ private static void searchStringArray(String[] arr) { for (long i = 0; i < capacity; i++) { int index = Array.BinarySearch(arr, arr[i]); } } private static void testLongValues() { Dictionary<long, long> dict = new Dictionary<long, long>(Int16.MaxValue); long[] arr = new long[capacity]; Stopwatch stopwatch = new Stopwatch(); Console.WriteLine("" + capacity + " Long values..."); stopwatch.Start(); populateLongDictionary(dict); stopwatch.Stop(); Console.WriteLine("Populate Long Dictionary: " + stopwatch.ElapsedMilliseconds); stopwatch.Reset(); stopwatch.Start(); populateLongArray(arr); stopwatch.Stop(); Console.WriteLine("Populate Long Array: " + stopwatch.ElapsedMilliseconds); stopwatch.Reset(); stopwatch.Start(); searchLongDictionary(dict); stopwatch.Stop(); Console.WriteLine("Search Long Dictionary: " + stopwatch.ElapsedMilliseconds); stopwatch.Reset(); stopwatch.Start(); searchLongArray(arr); stopwatch.Stop(); Console.WriteLine("Search Long Array: " + stopwatch.ElapsedMilliseconds); } /* Populate an array with long values. */ private static void populateLongArray(long[] arr) { for (long i = 0; i < capacity; i++) { arr[i] = i; } } /* Populate a dictionary with long key/value pairs. */ private static void populateLongDictionary(Dictionary<long, long> dict) { for (long i = 0; i < capacity; i++) { dict.Add(i, i); } } /* Search a Dictionary for each value in a range. */ private static void searchLongDictionary(Dictionary<long, long> dict) { for (long i = 0; i < capacity; i++) { long value = dict[i]; } } /* Do a binary search for each value in an array. */ private static void searchLongArray(long[] arr) { for (long i = 0; i < capacity; i++) { int index = Array.BinarySearch(arr, arr[i]); } } /** * Generate a random string of a given length. * Implementation from https://stackoverflow.com/a/1344258/1288 */ private static String generateRandomString(int length) { var chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"; var stringChars = new char[length]; var random = new Random(); for (int i = 0; i < stringChars.Length; i++) { stringChars[i] = chars[random.Next(chars.Length)]; } return new String(stringChars); } } </code></pre> <p>Here are the results with several different sizes of collections. (Times are in milliseconds.)</p> <blockquote> <p>500000 Long values...<br> Populate Long Dictionary: 26<br> Populate Long Array: 2<br> Search Long Dictionary: 9<br> Search Long Array: 80 </p> <p>500000 String values...<br> Populate String Array: 1237<br> Populate String Dictionary: 46<br> Sort String Array: 1755<br> Search String Dictionary: 27<br> Search String Array: 1569 </p> <p>1000000 Long values...<br> Populate Long Dictionary: 58<br> Populate Long Array: 5<br> Search Long Dictionary: 23<br> Search Long Array: 136 </p> <p>1000000 String values...<br> Populate String Array: 2070<br> Populate String Dictionary: 121<br> Sort String Array: 3579<br> Search String Dictionary: 58<br> Search String Array: 3267 </p> <p>3000000 Long values...<br> Populate Long Dictionary: 207<br> Populate Long Array: 14<br> Search Long Dictionary: 75<br> Search Long Array: 435 </p> <p>3000000 String values...<br> Populate String Array: 5553<br> Populate String Dictionary: 449<br> Sort String Array: 11695<br> Search String Dictionary: 194<br> Search String Array: 10594 </p> <p>10000000 Long values...<br> Populate Long Dictionary: 521<br> Populate Long Array: 47<br> Search Long Dictionary: 202<br> Search Long Array: 1181 </p> <p>10000000 String values...<br> Populate String Array: 18119<br> Populate String Dictionary: 1088<br> Sort String Array: 28174<br> Search String Dictionary: 747<br> Search String Array: 26503 </p> </blockquote> <p>And for comparison, here's the profiler output for the last run of the program (10 million records and lookups). I highlighted the relevant functions. They pretty closely agree with the Stopwatch timing metrics above.</p> <p><a href="https://i.stack.imgur.com/wzhDA.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/wzhDA.png" alt="Profiler output for 10 million records and lookups"></a></p> <p>You can see that the Dictionary lookups are much faster than binary search, and (as expected) the difference is more pronounced the larger the collection. So, if you have a reasonable hashing function (fairly quick with few collisions), a hash lookup should beat binary search for collections in this range.</p>

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