Python: список против Dict для таблицы поиска
У меня есть около 10 миллионов значений, которые мне нужно поместить в какую-то таблицу поиска, поэтому я подумал, что будет более эффективным списком или диктом?
Я знаю, что вы можете сделать что-то подобное для обоих:
if something in dict_of_stuff:
pass
а также
if something in list_of_stuff:
pass
Я думаю, что дикт будет быстрее и эффективнее.
Спасибо за вашу помощь.
РЕДАКТИРОВАТЬ 1
Немного больше информации о том, что я пытаюсь сделать. Задача Эйлера 92. Я создаю справочную таблицу, чтобы увидеть, все ли вычисленные значения уже рассчитаны.
РЕДАКТИРОВАТЬ 2
Эффективность для поиска.
РЕДАКТИРОВАТЬ 3
Нет значений, связанных со значением... так будет ли набор лучше?
8 ответов
скорость
Поиск в списках - 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 элементов), списки работают довольно хорошо.
Вы хотите диктовку.
Для (несортированных) списков в Python операция "in" требует времени O(n) - не очень хорошо, когда у вас большой объем данных. С другой стороны, dict - это хеш-таблица, поэтому вы можете ожидать O(1) времени поиска.
Как уже отмечали другие, вы можете вместо этого выбрать набор (особый тип dict), если у вас есть только ключи, а не пары ключ / значение.
Связанные с:
- Python wiki: информация о временной сложности контейнерных операций Python.
- SO: время работы контейнера Python и сложности памяти
В качестве нового набора тестов для показа @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 об уникальности: если у ОП есть 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]})
С этим диктом можно знать:
- Если значение было в исходном наборе данных (т.е.
2 in dвозвращаетсяTrue) - Где значение было в исходном наборе данных (т.е.
d[2]возвращает список индексов, где данные были найдены в исходном списке данных:[1, 4])
Если данные уникальны, set() будет наиболее эффективным, но из двух - dict (что также требует уникальности, упс:)
На самом деле вам не нужно хранить 10 миллионов значений в таблице, так что в любом случае это не имеет большого значения.
Подсказка: подумайте, насколько большим может быть ваш результат после первой операции с квадратами. Максимально возможный результат будет намного меньше, чем 10 миллионов...