Оптимизация поиска:Поиск по ключам в словаре против.Поиск по индексу массива

StackOverflow https://stackoverflow.com/questions/908050

  •  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), но это потому, что словарь реализован как хеш-таблица, поэтому вам нужно сначала вычислить значение хеш-функции, чтобы узнать, какой элемент возвращать.Хэш-таблицы часто не так эффективны, но они хороши для больших наборов данных или наборов данных, которые имеют много уникальных хеш-значений.

Список (не говоря уже о том, что это мусорное слово, используемое для описания массива, а не связанного списка!) будет быстрее, поскольку он вернет значение, напрямую вычислив элемент, который вы хотите вернуть.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top