У меня есть около 10 миллионов значений, которые мне нужно поместить в какую-то таблицу поиска, так что мне было интересно, какой из них будет более эффективным - список или дикт ?
Я знаю, что вы можете сделать что-то подобное для обоих:
if something in dict_of_stuff:
pass
и
if something in list_of_stuff:
pass
Я думаю, что дикт будет быстрее и эффективнее.
Спасибо за вашу помощь.
РЕДАКТИРОВАТЬ 1
Немного больше информации о том, что я пытаюсь сделать. Задача Эйлера 92 . Я создаю справочную таблицу, чтобы увидеть, все ли вычисленные значения уже рассчитаны.
РЕДАКТИРОВАТЬ 2
Эффективность для поиска.
РЕДАКТИРОВАТЬ 3
Нет значений, связанных со значением ... так что набор будет лучше?
Ответы:
скорость
Поиск в списках - O (n), поиск в словарях - амортизированный O (1) с учетом количества элементов в структуре данных. Если вам не нужно связывать значения, используйте наборы.
объем памяти
И словари, и наборы используют хеширование и используют гораздо больше памяти, чем только для хранения объектов. По словам AM Kuchling из Beautiful Code , реализация пытается сохранить хэш 2/3 заполненным, так что вы можете потратить довольно много памяти.
Если вы не добавляете новые записи «на лету» (что вы делаете, основываясь на обновленном вопросе), возможно, стоит отсортировать список и использовать бинарный поиск. Это O (log n) и, вероятно, будет медленнее для строк, невозможно для объектов, которые не имеют естественного упорядочения.
источник
Диктовка - это хеш-таблица, поэтому очень быстро найти ключи. Таким образом, между dict и list, dict будет быстрее. Но если у вас нет значения для связывания, еще лучше использовать набор. Это хеш-таблица, без части «таблица».
РЕДАКТИРОВАТЬ: для вашего нового вопроса, да, набор будет лучше. Просто создайте 2 набора, один для последовательностей, оканчивающихся на 1, и другой для последовательностей, оканчивающихся на 89. Я успешно решил эту проблему с помощью наборов.
источник
set()
это именно то, что вы хотите. O (1) поисков, и меньше, чем dict.источник
Я провел несколько сравнительных тестов, и оказалось, что 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 элементов), списки работают довольно хорошо.
источник
-s
опция заключается в настройкеtimeit
среды, т.е. она не учитывается в общем времени.-s
Опция выполняется только один раз. На Python 3.3 я получаю следующие результаты: gen (range) -> 0,229 usec, список -> 157 мс, dict -> 0,0806 usec, набор -> 0,0807 usec. Набор и диктовка производительности одинаковы. Однако для инициализации Dict требуется немного больше времени, чем установлено (общее время 13.580 с. 11.803 с)python -mtimeit -s "d=set(range(10**7))" "5*10**6 in d"
использовании Python 3.6.0 (10000000 циклов, лучшее из 3: 0,0608 мксек на цикл), примерно столько же, сколько в тесте dict, так что спасибо за ваш комментарий.Вы хотите диктовку.
Для (несортированных) списков в Python операция «in» требует времени O (n) - не очень хорошо, если у вас большой объем данных. С другой стороны, dict - это хеш-таблица, поэтому вы можете ожидать O (1) времени поиска.
Как уже отмечали другие, вы можете вместо этого выбрать набор (особый тип dict), если у вас есть только ключи, а не пары ключ / значение.
Связанный:
источник
in
оператор, примененный к отсортированному списку, работает лучше, чем при применении к несортированному списку (для поиска случайного значения)? (Я не думаю, уместны ли они внутри как векторы или как узлы в связанном списке.)если данные уникальны, set () будет наиболее эффективным, но из двух - dict (что также требует уникальности, упс :)
источник
В качестве нового набора тестов для показа @ EriF89 все еще прав после всех этих лет:
Здесь мы также сравниваем a
tuple
, который, как известно, быстрееlists
(и использует меньше памяти) в некоторых случаях использования. В случае справочной таблицы,tuple
сработало не лучше.И то,
dict
и другоеset
очень хорошо. Это поднимает интересный момент, связанный с ответом @SilentGhost об уникальности: если у OP есть 10M значений в наборе данных, и неизвестно, есть ли в них дубликаты, тогда было бы целесообразно сохранить набор / указание его элементов параллельно с фактическим набором данных, и проверка на существование в этом наборе / dict. Возможно, что 10M точек данных имеют только 10 уникальных значений, что значительно меньше места для поиска!Ошибка SilentGhost в отношении dicts на самом деле освещается тем, что можно использовать dict для корреляции дублированных данных (в значениях) в недублированный набор (ключи) и, таким образом, сохранить один объект данных для хранения всех данных, но при этом оставаться быстрым как справочная таблица. Например, ключом dict может быть искомое значение, а значением может быть список индексов в воображаемом списке, где это значение встречается.
Например, если список исходных данных для поиска был
l=[1,2,3,1,2,1,4]
, его можно оптимизировать как для поиска, так и для памяти, заменив его следующим:С этим диктом можно знать:
2 in d
возвращаетTrue
)d[2]
возвращает список индексов , где данные были найдены в первоначальном списке данных:[1, 4]
)источник
На самом деле вам не нужно хранить 10 миллионов значений в таблице, так что в любом случае это не имеет большого значения.
Подсказка: подумайте, насколько большим может быть ваш результат после первой операции с квадратами. Максимально возможный результат будет намного меньше, чем 10 миллионов ...
источник