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

Question

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

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

if something in dict_of_stuff:
    pass

и

if something in list_of_stuff:
    pass

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

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

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

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

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

Answer 1

Скорость

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

Память

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

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

Answer 2

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

---

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

Answer 3

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

Answer 4

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

Answer 5

Вы хотите диктовать.

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

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

Связанный:

• Python wiki : информация о временной сложности контейнерных операций Python.
• SO : время работы контейнера Python и сложность памяти

Answer 6

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

Answer 7

Как новый набор тестов для показа, @ 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

Здесь мы также сравниваем 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])

Answer 8

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

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