Для очень маленьких коллекций разница будет незначительной. В нижней части вашего диапазона (500 тыс. Предметов) вы начнете видеть разницу, если вы делаете много поисков. Бинарный поиск будет O (log n), тогда как поиск по хешу будет O (1), амортизируется . Это не то же самое, что действительно константа, но вам все равно придется иметь довольно ужасную хеш-функцию, чтобы получить худшую производительность, чем бинарный поиск.
(Когда я говорю «ужасный хэш», я имею в виду что-то вроде:
hashCode()
{
return 0;
}
Да, он сам по себе очень быстрый, но превращает вашу хэш-карту в связанный список.)
ialiashkevich написал некоторый код C #, используя массив и словарь для сравнения двух методов, но он использовал длинные значения для ключей. Я хотел протестировать что-то, что фактически выполняло бы хеш-функцию во время поиска, поэтому я изменил этот код. Я изменил его, чтобы использовать значения String, и я реорганизовал разделы заполнения и поиска в свои собственные методы, чтобы их было легче увидеть в профилировщике. Я также оставил в коде, который использовал значения Long, просто для сравнения. Наконец, я избавился от пользовательской функции двоичного поиска и использовал ее в классе Array.
Вот этот код:
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);
}
}
Вот результаты с несколькими различными размерами коллекций. (Время указывается в миллисекундах.)
500000 Длинные значения ...
Заполните длинный словарь: 26
Заполните длинный массив: 2
Поиск длинного словаря: 9
Поиск длинного массива: 80
500000 Строковые значения ...
Заполнить строковый массив: 1237
Заполните словарь строк: 46
Массив строк сортировки: 1755
Поиск строки словаря: 27
Массив строк поиска: 1569
1000000 Длинные значения ...
Заполните длинный словарь: 58
Заполните длинный массив: 5
Поиск длинного словаря: 23
Поиск длинного массива: 136
1000000 Строковые значения ...
Заполнить строковый массив: 2070
Заполните словарь строк: 121
Массив строк сортировки: 3579
Поиск строки словаря: 58
Массив строк поиска: 3267
3000000 Длинные значения ...
Заполните длинный словарь: 207
Заполните длинный массив: 14
Поиск длинного словаря: 75
Поиск длинного массива: 435
3000000 Строковые значения ...
Заполните массив строк: 5553
Заполните словарь строк: 449
Массив строк сортировки: 11695
Поиск строки словарь: 194
Массив строк поиска: 10594
10000000 Длинные значения ...
Заполните длинный словарь: 521
Заполните длинный массив: 47
Поиск длинного словаря: 202
Длинный массив поиска: 1181
10000000 Строковые значения ...
Заполнить строковый массив: 18119
Заполните словарь строк: 1088
Массив строк сортировки: 28174
Поиск строки словаря: 747
Массив строк поиска: 26503
И для сравнения, вот вывод профилировщика для последнего запуска программы (10 миллионов записей и поисков). Я выделил соответствующие функции. Они довольно близко согласуются с метриками хронометража секундомера выше.
Вы можете видеть, что поиск по словарю выполняется намного быстрее, чем бинарный поиск, и (как и ожидалось) различие тем сильнее, чем больше коллекция. Таким образом, если у вас есть разумная функция хеширования (довольно быстрая, с небольшим количеством коллизий), поиск по хешу должен превзойти двоичный поиск коллекций в этом диапазоне.