Почему поиск в dict всегда лучше, чем просмотр списка?

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

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

Итак, возникает вопрос: Почему поиск списков выполняется так плохо? Что мне не хватает?

По второму вопросу что-то еще, что вызывало мое внимание, было небольшим "разрывом" в времени поиска dict после примерно 1000 записей. Я отобразил время поиска dict, чтобы показать его.

ps1 Я знаю об O (n) vs O (1) время амортизации для массивов и хэш-таблиц, но обычно бывает, что для небольшого числа элементов, итерации по массиву, лучше, чем использование хеш-таблицы.

p.s.2 Вот код, который я использовал для сравнения времени поиска dict и списка:

import timeit

lengths = [2 ** i for i in xrange(15)]

list_time = []
dict_time = []
for l in lengths:
    list_time.append(timeit.timeit('%i in d' % (l/2), 'd=range(%i)' % l))
    dict_time.append(timeit.timeit('%i in d' % (l/2),
                                   'd=dict.fromkeys(range(%i))' % l))
    print l, list_time[-1], dict_time[-1]

p.s.3 Использование Python 2.7.13

Ответ 1

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

Доступ к нескольким элементам массива дешев, конечно, но вычисление == на удивление тяжело в Python. Посмотрите на этот всплеск на втором графике? Это стоимость вычисления == для двух ints там.

Поиск в списке должен вычислять == намного больше, чем ваши запросы в dict.

Между тем, вычислительные хэши могут быть довольно тяжелой операцией для множества объектов, но для всех задействованных здесь ints они просто хешируют для себя. (-1 будет hash до -2, а большие целые числа (технически long s) будут хешировать с меньшими целыми числами, но здесь это не применимо.)

Поиск в Dict на самом деле не так уж и плох в Python, особенно когда ваши ключи - это всего лишь ряд диапазонов int. Все ints здесь hash для себя, и Python использует настраиваемую схему открытой адресации вместо цепочки, поэтому все ваши ключи оказываются почти такими же непрерывными в памяти, как если бы вы использовали список (то есть указатели на конец ключа в непрерывном диапазоне PyDictEntry s). Процедура поиска выполняется быстро, и в ваших тестовых случаях она всегда попадает в правую клавишу на первом зонде.

Хорошо, вернемся к шипу в графе 2. Шип в временах поиска на 1024 элементах во втором графике объясняется тем, что для всех меньших размеров целые числа, которые вы искали, были <= 256, поэтому все они падали в пределах небольшого целочисленного кеша CPython. Эталонная реализация Python сохраняет канонические целые объекты для всех целых чисел от -5 до 256 включительно. Для этих целых чисел Python смог использовать быстрое сравнение указателей, чтобы избежать прохождения (удивительно тяжеловесного) процесса вычисления ==. Для больших целых аргументов аргумент in больше не был тем же объектом, что и целочисленное целое в dict, а Python должен был пройти весь процесс ==.

Ответ 2

Короткий ответ заключается в том, что списки используют линейный поиск, а dicts использует апробированный поиск O (1).

Кроме того, запросы dict могут пропускать тест равенства, когда 1) значения хэша не совпадают или 2) при совпадении идентичности. Списки используют только преимущества идентификации - подразумевает оптимизацию равенства.

Еще в 2008 году я поговорил по этому вопросу, где вы найдете все подробности: https://www.youtube.com/watch?v=hYUsssClE94

Примерно логика для поиска списков:

for element in s:
    if element is target:
        # fast check for identity implies equality
        return True
    if element == target:
        # slower check for actual equality
        return True
return False

Для dicts логика примерно:

h = hash(target)
for i in probe_sequence(h, len(table)):
    element = key_table[i]
    if element is UNUSED:
        raise KeyError(target)
    if element is target:
        # fast path for identity implies equality
        return value_table[i]
    if h != h_table[i]:
        # unequal hashes implies unequal keys
        continue
    if element == target:
        # slower check for actual equality
        return value_table[i]

Таблицы хеш-словаря обычно составляют от одной трети до двух третей, поэтому они имеют тенденцию иметь несколько коллизий (несколько отключений вокруг цикла, показанного выше) независимо от размера. Кроме того, проверка значения хеша предотвращает ненужные медленные проверки на равенство (вероятность пропущенной проверки равен примерно 1 в 2 ** 64).

Если ваше время фокусируется на целых числах, в игре есть и другие эффекты. Этот хэш int - это int int, поэтому хеширование происходит очень быстро. Кроме того, это означает, что если вы сохраняете последовательные целые числа, обычно не возникает никаких столкновений.

Ответ 3

Вы говорите, что "доступ к нескольким элементам в массиве быстрее, чем вычисление хэша".

Простое правило хэширования для строк может быть просто суммой (с по модулем в конце). Это нераспространяемая операция, которая может сравниться с сравнениями символов, особенно когда существует длинное совпадение в префиксе.