Оптимизация поиска: поиск по словарю или поиск по массиву

Question

Я пишу 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) поисков в худшем случае, поэтому я ожидаю, что поиск в массиве будет быстрее, но не настолько сильно!

В настоящее время я храню рейтинг покерных рук в Словаре. Я полагаю, если это так быстро, как это возможно при поиске в словаре, мне придется переосмыслить свой подход и вместо этого использовать массивы, хотя индексация рейтинга будет немного сложнее, и мне, вероятно, придется задать еще один вопрос по этому поводу.

Answer 1

Не забывайте, что нотации Big-O говорят только о том, как возрастает сложность по отношению к размеру (и т. Д.) - это не дает никаких указаний на постоянные факторы. Вот почему иногда даже линейный поиск для ключей выполняется быстрее, чем поиск по словарю, когда ключей достаточно мало. В этом случае вы даже не выполняете поиск по массиву - просто прямая операция индексации.

Для прямого поиска по индексу массивы в основном идеальны - это просто случай

pointer_into_array = base_pointer + offset * size

(А затем разыменование указателя.)

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

Как всегда, выберите правильную структуру данных для задания - и если вам действительно удастся с легкостью просто индексировать в массив (или List<T>), тогда да, это будет невероятно быстро.

Answer 2

Ожидается ли этот тип поведения (снижение производительности в 8 раз)?

Почему бы и нет? Каждый поиск в массиве является почти мгновенным / незначительным, тогда как для поиска в словаре может потребоваться как минимум дополнительный вызов подпрограммы.

Смысл того, что оба они являются O (1), означает, что даже если у вас в 50 раз больше предметов в каждой коллекции, снижение производительности все равно остается лишь фактором (8).

Answer 3

Что-то может занять тысячелетие, и все равно быть О (1).

Если вы пошагово пройдете этот код в окне разборки, вы быстро поймете, в чем разница.

Answer 4

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

На заметку о реализации; в .NET словари по сути являются хешами. Вы можете несколько улучшить их производительность поиска ключей, гарантируя, что ваши ключи хешируются в большом пространстве уникальных значений. Похоже, что в вашем случае вы используете простое целое число в качестве ключа (который, я считаю, хэширует его собственную ценность), так что это может быть лучшим, что вы можете сделать.

Answer 5

Добро пожаловать в систему обозначений Big-O. Вы всегда должны учитывать, что существует постоянный фактор.

Выполнение одного Dict-Lookup, конечно, намного дороже, чем поиск в массиве.

Big-O говорит только о том, как масштабируются алгоритмы. Удвойте количество поисков и посмотрите, как меняются числа: оба должны занять примерно вдвое больше времени.

Answer 6

Поиск в массиве - это самая быстрая вещь, которую вы можете сделать - по сути, это всего лишь один бит арифметики указателя для перехода от начала массива к элементу, который вы хотите найти. С другой стороны, поиск в словаре, вероятно, будет несколько медленнее, поскольку он должен выполнять хеширование и заботиться о поиске правильного сегмента. Хотя ожидаемое время выполнения также равно O (1), алгоритмические константы больше, поэтому он будет медленнее.

Answer 7

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

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