Python: список против Dict для таблицы поиска

169

У меня есть около 10 миллионов значений, которые мне нужно поместить в какую-то таблицу поиска, так что мне было интересно, какой из них будет более эффективным - список или дикт ?

Я знаю, что вы можете сделать что-то подобное для обоих:

if something in dict_of_stuff:
    pass

и

if something in list_of_stuff:
    pass

Я думаю, что дикт будет быстрее и эффективнее.

Спасибо за вашу помощь.

РЕДАКТИРОВАТЬ 1
Немного больше информации о том, что я пытаюсь сделать. Задача Эйлера 92 . Я создаю справочную таблицу, чтобы увидеть, все ли вычисленные значения уже рассчитаны.

РЕДАКТИРОВАТЬ 2
Эффективность для поиска.

РЕДАКТИРОВАТЬ 3
Нет значений, связанных со значением ... так что набор будет лучше?

Нет
источник
1
Эффективность с точки зрения чего? Вставить? Уважать? Потребление памяти? Вы проверяете наличие чистого значения или с ним связаны какие-либо метаданные?
Truppo
Как примечание: вам не нужен список из 10 миллионов или диктовка для этой конкретной проблемы, но гораздо меньший.
sfotiadis

Ответы:

222

скорость

Поиск в списках - O (n), поиск в словарях - амортизированный O (1) с учетом количества элементов в структуре данных. Если вам не нужно связывать значения, используйте наборы.

объем памяти

И словари, и наборы используют хеширование и используют гораздо больше памяти, чем только для хранения объектов. По словам AM Kuchling из Beautiful Code , реализация пытается сохранить хэш 2/3 заполненным, так что вы можете потратить довольно много памяти.

Если вы не добавляете новые записи «на лету» (что вы делаете, основываясь на обновленном вопросе), возможно, стоит отсортировать список и использовать бинарный поиск. Это O (log n) и, вероятно, будет медленнее для строк, невозможно для объектов, которые не имеют естественного упорядочения.

Торстен Марек
источник
6
Да, но это разовая операция, если содержимое никогда не меняется. Двоичный поиск - O (log n).
Торстен Марек
1
@John Fouhy: целые числа хранятся не в хеш-таблице, а только в указателях, т. Е. У вас есть 40M для целых (ну, не совсем, когда их много) и 60M для хеш-таблицы. Я согласен, что в настоящее время это не такая уж большая проблема, но все же стоит иметь в виду.
Торстен Марек
2
Это старый вопрос, но я думаю, что амортизированный O (1) может не выполняться для очень больших сетов / диктов. В худшем случае согласно wiki.python.org/moin/TimeComplexity это O (n). Я предполагаю, что это зависит от реализации внутреннего хеширования, в какой момент среднее время отклоняется от O (1) и начинает сходиться к O (n). Вы можете повысить производительность поиска, разбив глобальные наборы на более мелкие разделы на основе некоторого легко различимого атрибута (например, значения первой цифры, затем второй, третьей и т. Д., Пока вам нужно получить оптимальный размер набора). ,
Nisan.H
3
@TorstenMarek Это меня смущает. На этой странице поиск по списку - O (1), а поиск по диктату - O (n), что противоположно тому, что вы сказали. Я неправильно понимаю?
temporary_user_name
3
@ Aerovistae Я думаю, вы неправильно прочитали информацию на этой странице. Под списком я вижу O (n) для "x in s" (поиск). Он также показывает набор и диктовку в виде среднего значения O (1).
Деннис
45

Диктовка - это хеш-таблица, поэтому очень быстро найти ключи. Таким образом, между dict и list, dict будет быстрее. Но если у вас нет значения для связывания, еще лучше использовать набор. Это хеш-таблица, без части «таблица».


РЕДАКТИРОВАТЬ: для вашего нового вопроса, да, набор будет лучше. Просто создайте 2 набора, один для последовательностей, оканчивающихся на 1, и другой для последовательностей, оканчивающихся на 89. Я успешно решил эту проблему с помощью наборов.

nosklo
источник
35

set()это именно то, что вы хотите. O (1) поисков, и меньше, чем dict.

рекурсивный
источник
31

Я провел несколько сравнительных тестов, и оказалось, что dict быстрее, чем список и набор для больших наборов данных, на Python 2.7.3 на процессоре i7 в Linux:

  • python -mtimeit -s 'd=range(10**7)' '5*10**6 in d'

    10 циклов, лучшее из 3: 64,2 мсек на цикл

  • python -mtimeit -s 'd=dict.fromkeys(range(10**7))' '5*10**6 in d'

    10000000 циклов, лучшее из 3: 0,0759 юзек на цикл

  • python -mtimeit -s 'from sets import Set; d=Set(range(10**7))' '5*10**6 in d'

    1000000 петель, лучшее из 3: 0,262 мксек на петлю

Как видите, dict значительно быстрее списка и примерно в 3 раза быстрее, чем установленный. В некоторых приложениях вы все равно можете выбрать набор для красоты. И если наборы данных действительно малы (<1000 элементов), списки работают довольно хорошо.

EriF89
источник
Не должно ли быть с точностью до наоборот? Список: 10 * 64.2 * 1000 = 642000 usec, dict: 10000000 * 0.0759 = 759000 usec и set: 1000000 * 0.262 = 262000 usec ... поэтому наборы являются самыми быстрыми, за ними следует список и с dict как последним в вашем примере. Или я что-то упустил?
andzep
1
... но вопрос для меня здесь: что на самом деле измеряет это время? Не время доступа к заданному списку, диктату или набору, но гораздо больше времени и циклов для создания списка, диктовки, набора и, наконец, для поиска и доступа к одному значению. Итак, это имеет отношение к вопросу вообще? ... Это интересно, хотя ...
andzep
8
@andzep, вы ошибаетесь, -sопция заключается в настройке timeitсреды, т.е. она не учитывается в общем времени. -sОпция выполняется только один раз. На Python 3.3 я получаю следующие результаты: gen (range) -> 0,229 usec, список -> 157 мс, dict -> 0,0806 usec, набор -> 0,0807 usec. Набор и диктовка производительности одинаковы. Однако для инициализации Dict требуется немного больше времени, чем установлено (общее время 13.580 с. 11.803 с)
sleblanc
1
почему бы не использовать встроенный набор? Я на самом деле получаю намного худшие результаты с сетами. Set (), чем со встроенной сетью ()
Томас Гайот-Сионнест
2
@ ThomasGuyot-Sionnest Встроенный набор был введен в Python 2.4, поэтому я не уверен, почему я не использовал его в предложенном решении. Я получаю хорошую производительность при python -mtimeit -s "d=set(range(10**7))" "5*10**6 in d"использовании Python 3.6.0 (10000000 циклов, лучшее из 3: 0,0608 мксек на цикл), примерно столько же, сколько в тесте dict, так что спасибо за ваш комментарий.
EriF89
6

Вы хотите диктовку.

Для (несортированных) списков в Python операция «in» требует времени O (n) - не очень хорошо, если у вас большой объем данных. С другой стороны, dict - это хеш-таблица, поэтому вы можете ожидать O (1) времени поиска.

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

Связанный:

  • Python wiki : информация о временной сложности контейнерных операций Python.
  • SO : время работы контейнера Python и сложности памяти
zweiterlinde
источник
1
Даже для отсортированных списков «in» - это O (n).
2
Для связанного списка, да --- но "списки" в Python - это то, что большинство людей назвали бы векторами, которые обеспечивают индексированный доступ в O (1) и операцию поиска в O (log n) при сортировке.
Цвайтерлинде
Вы говорите, что inоператор, примененный к отсортированному списку, работает лучше, чем при применении к несортированному списку (для поиска случайного значения)? (Я не думаю, уместны ли они внутри как векторы или как узлы в связанном списке.)
martineau
4

если данные уникальны, set () будет наиболее эффективным, но из двух - dict (что также требует уникальности, упс :)

SilentGhost
источник
я понял, когда увидел, что мой ответ опубликован%)
SilentGhost
2
@SilentGhost, если ответ неправильный, почему бы не удалить его? слишком плохо для голосов, но это случается (ну, случилось )
Жан-Франсуа Фабр
3

В качестве нового набора тестов для показа @ EriF89 все еще прав после всех этих лет:

$ python -m timeit -s "l={k:k for k in xrange(5000)}"    "[i for i in xrange(10000) if i in l]"
1000 loops, best of 3: 1.84 msec per loop
$ python -m timeit -s "l=[k for k in xrange(5000)]"    "[i for i in xrange(10000) if i in l]"
10 loops, best of 3: 573 msec per loop
$ python -m timeit -s "l=tuple([k for k in xrange(5000)])"    "[i for i in xrange(10000) if i in l]"
10 loops, best of 3: 587 msec per loop
$ python -m timeit -s "l=set([k for k in xrange(5000)])"    "[i for i in xrange(10000) if i in l]"
1000 loops, best of 3: 1.88 msec per loop

Здесь мы также сравниваем a tuple, который, как известно, быстрее lists(и использует меньше памяти) в некоторых случаях использования. В случае справочной таблицы, tupleсработало не лучше.

И то, dictи другое setочень хорошо. Это поднимает интересный момент, связанный с ответом @SilentGhost об уникальности: если у OP есть 10M значений в наборе данных, и неизвестно, есть ли в них дубликаты, тогда было бы целесообразно сохранить набор / указание его элементов параллельно с фактическим набором данных, и проверка на существование в этом наборе / dict. Возможно, что 10M точек данных имеют только 10 уникальных значений, что значительно меньше места для поиска!

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

Например, если список исходных данных для поиска был l=[1,2,3,1,2,1,4], его можно оптимизировать как для поиска, так и для памяти, заменив его следующим:

>>> from collections import defaultdict
>>> d = defaultdict(list)
>>> l=[1,2,3,1,2,1,4]
>>> for i, e in enumerate(l):
...     d[e].append(i)
>>> d
defaultdict(<class 'list'>, {1: [0, 3, 5], 2: [1, 4], 3: [2], 4: [6]})

С этим диктом можно знать:

  1. Если значение было в исходном наборе данных (т.е. 2 in dвозвращает True)
  2. Если значение было в исходном наборе данных (т.е. d[2]возвращает список индексов , где данные были найдены в первоначальном списке данных: [1, 4])
hamx0r
источник
Для вашего последнего параграфа, хотя и имеет смысл читать его, было бы неплохо (и, вероятно, легче понять) увидеть фактический код, который вы пытаетесь объяснить.
Кайзер
0

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

Подсказка: подумайте, насколько большим может быть ваш результат после первой операции с квадратами. Максимально возможный результат будет намного меньше, чем 10 миллионов ...

Kiv
источник