Оптимизация поиска:Поиск по ключам в словаре против.Поиск по индексу массива
-
05-09-2019 - |
Вопрос
Я пишу программу для оценки 7-карточных покерных комбинаций, это один из моих любимых проектов.Пытаясь оптимизировать его скорость (мне нравится эта задача), я был шокирован, обнаружив, что производительность поиска по ключам в словаре была довольно низкой по сравнению с поиском по индексу массива.
Например, я запустил этот пример кода, который пересчитывает все 52 варианта выбора 7 = 133 784 560 возможных 7-карточных комбинаций:
var intDict = new Dictionary<int, int>();
var intList = new List<int>();
for (int i = 0; i < 100000; i ++)
{
intDict.Add(i, i);
intList.Add(i);
}
int result;
var sw = new Stopwatch();
sw.Start();
for (int card1 = 0; card1 < 46; card1++)
for (int card2 = card1 + 1; card2 < 47; card2++)
for (int card3 = card2 + 1; card3 < 48; card3++)
for (int card4 = card3 + 1; card4 < 49; card4++)
for (int card5 = card4 + 1; card5 < 50; card5++)
for (int card6 = card5 + 1; card6 < 51; card6++)
for (int card7 = card6 + 1; card7 < 52; card7++)
result = intDict[32131]; // perform C(52,7) dictionary key lookups
sw.Stop();
Console.WriteLine("time for dictionary lookups: {0} ms", sw.ElapsedMilliseconds);
sw.Reset();
sw.Start();
for (int card1 = 0; card1 < 46; card1++)
for (int card2 = card1 + 1; card2 < 47; card2++)
for (int card3 = card2 + 1; card3 < 48; card3++)
for (int card4 = card3 + 1; card4 < 49; card4++)
for (int card5 = card4 + 1; card5 < 50; card5++)
for (int card6 = card5 + 1; card6 < 51; card6++)
for (int card7 = card6 + 1; card7 < 52; card7++)
result = intList[32131]; // perform C(52,7) array index lookups
sw.Stop();
Console.WriteLine("time for array index lookups: {0} ms", sw.ElapsedMilliseconds);
который выводит:
time for dictionary lookups: 2532 ms
time for array index lookups: 313 ms
Ожидается ли такое поведение (снижение производительности в 8 раз)?IIRC, словарь в среднем имеет поиск O (1), тогда как массив имеет поиск в худшем случае O (1), поэтому я ожидаю, что поиск в массиве будет быстрее, но не настолько!
В настоящее время я храню рейтинги покерных комбинаций в словаре.Я полагаю, что если это будет так быстро, как поиск по словарю, мне придется переосмыслить свой подход и вместо этого использовать массивы, хотя индексирование рейтингов станет немного сложнее, и мне, вероятно, придется задать еще один вопрос по этому поводу.
Решение
Не забывайте, что нотации Big-O говорят только о том, как сложность возрастает в зависимости от размера (и т. д.), но не дают никаких указаний на постоянные факторы, участвующие в этом процессе.Вот почему иногда даже линейная поиск for ключей выполняется быстрее, чем поиск по словарю, если ключей достаточно мало.В этом случае вы даже не выполняете поиск по массиву — просто операция индексации.
Для прямого поиска по индексу массивы, по сути, идеальны – это всего лишь случай
pointer_into_array = base_pointer + offset * size
(А затем разыменование указателя.)
Выполнение поиска по словарю относительно сложно — очень быстро по сравнению (скажем) с линейным поиском по ключу, когда ключей много, но гораздо сложнее, чем прямой поиск по массиву.Он должен вычислить хеш ключа, затем определить, в каком сегменте он должен находиться, возможно, иметь дело с повторяющимися хэшами (или повторяющимися сегментами), а затем проверить на равенство.
Как всегда, выберите правильную структуру данных для задания – и если вам действительно удастся обойтись простой индексацией в массив (или List<T>
) тогда да, это будет ослепительно быстро.
Другие советы
Ожидается ли такое поведение (снижение производительности в 8 раз)?
Почему нет?Каждый поиск в массиве происходит почти мгновенно и практически не требует внимания, тогда как поиск по словарю может потребовать как минимум дополнительного вызова подпрограммы.
То, что оба они равны O(1), означает, что даже если у вас в каждой коллекции в 50 раз больше элементов, снижение производительности все равно будет лишь фактором, каким бы он ни был (8).
Что-то может занять тысячелетие и все равно оставаться O(1).
Если вы выполните этот код в окне дизассемблирования за один шаг, вы быстро поймете, в чем разница.
Словарные структуры наиболее полезны, когда пространство ключей очень велико и не может быть отображено в стабильном, упорядоченном порядке.Если вы сможете преобразовать свои ключи в простое целое число в относительно небольшом диапазоне, вам будет сложно найти структуру данных, которая будет работать лучше, чем массив.
На заметке о реализации;в .NET словари по сути являются хешируемыми.Вы можете несколько улучшить производительность поиска ключей, гарантируя, что ваши ключи хэшируются в большое пространство уникальных значений.Похоже, что в вашем случае вы используете простое целое число в качестве ключа (который, как я считаю, хеширует свое собственное значение) - так что это может быть лучшее, что вы можете сделать.
Поиск в массиве — это самое быстрое, что вы можете сделать — по сути, все, что вам нужно, — это один бит арифметических действий с указателями, чтобы пройти от начала массива до элемента, который вы хотите найти.С другой стороны, поиск по словарю, вероятно, будет несколько медленнее, поскольку ему необходимо выполнять хеширование и искать правильный сегмент.Хотя ожидаемое время выполнения также равно O(1) — алгоритмические константы больше, поэтому оно будет медленнее.
Добро пожаловать в нотацию Big-O.Всегда нужно учитывать, что здесь присутствует постоянный фактор.
Выполнение одного Dict-Lookup, конечно, намного дороже, чем поиск в массиве.
Big-O говорит только о том, как масштабируются алгоритмы.Удвойте количество запросов и посмотрите, как изменяются числа:И то, и другое должно занять примерно вдвое больше времени.
Стоимость извлечения элемента из Словарь O(1), но это потому, что словарь реализован как хеш-таблица, поэтому вам нужно сначала вычислить значение хеш-функции, чтобы узнать, какой элемент возвращать.Хэш-таблицы часто не так эффективны, но они хороши для больших наборов данных или наборов данных, которые имеют много уникальных хеш-значений.
Список (не говоря уже о том, что это мусорное слово, используемое для описания массива, а не связанного списка!) будет быстрее, поскольку он вернет значение, напрямую вычислив элемент, который вы хотите вернуть.