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

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

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

if something in dict_of_stuff:
    pass

и

if something in list_of_stuff:
    pass

Моя мысль - это дикт будет быстрее и эффективнее.

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

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

ИЗМЕНИТЬ 2
Эффективность поиска.

ИЗМЕНИТЬ 3
Нет значений, ассоциированных со значением... так лучше было бы set?

Ответы

Ответ 1

Скорость

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

Память

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

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

Ответ 2

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

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

Ответ 3

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

Ответ 4

Я сделал некоторый бенчмаркинг, и выяснилось, что dict быстрее, чем список, и устанавливает для больших наборов данных, запуская python 2.7.3 на i7 CPU на 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 usec за цикл

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

    1000000 циклов, лучше всего 3: 0.262 usec за цикл

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

Ответ 5

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

Ответ 6

Вам нужен дикт.

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

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

по теме:

  • Python wiki: информация о временной сложности операций с контейнерами Python.
  • fooobar.com/questions/53457/...: время работы контейнера с интерфейсом Python и его сложности

Ответ 7

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

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