Самый быстрый способ поиска списка в Python

Question

Когда вы делаете что-то вроде "test" in a, где a - список, Python выполняет последовательный поиск в списке или создает представление хеш-таблицы для оптимизации поиска? В приложении мне это нужно, потому что я буду много искать в списке, так что лучше будет сделать что-то вроде b = set(a), а затем "test" in b? Также обратите внимание, что в списке значений, которые у меня будут, не будет дубликатов данных, и мне не важно, в каком порядке они находятся; Мне просто нужно иметь возможность проверить наличие значения.

Answer 1

Также обратите внимание, что в списке значений, которые у меня будут, не будет дубликатов данных, и мне на самом деле все равно, в каком порядке они находятся; Мне просто нужно иметь возможность проверить наличие значения.

Не используйте список, вместо него используйте set(). У него есть именно те свойства, которые вам нужны, включая невероятно быстрый in тест.

Я видел ускорения в 20 раз и более в местах (в основном, с большим числом ошибок), где один список был изменен для набора.

Answer 2

"test" in a со списком a выполнит линейный поиск. Настройка хеш-таблицы на лету будет намного дороже, чем линейный поиск. "test" in b, с другой стороны, выполнит поиск хеша с аморитизированным O (1).

В описываемом вами случае, похоже, нет причин использовать список поверх набора.

Answer 3

Я думаю, что было бы лучше пойти с установленной реализацией. Я точно знаю, что наборы имеют O (1) время поиска. Я думаю, что списки занимают O (N) время поиска. Но даже если списки также являются поиском O (1), вы ничего не потеряете, переключившись на наборы.

Кроме того, наборы не допускают дублирования значений. Это также сделает вашу программу немного более эффективной в использовании памяти

Answer 4

Список и кортежи, по-видимому, имеют одинаковое время, и использование «in» медлено для больших данных:

>>> t = list(range(0, 1000000))
>>> a=time.time();x = [b in t for b in range(100234,101234)];print(time.time()-a)
1.66235494614
>>> t = tuple(range(0, 1000000))
>>> a=time.time();x = [b in t for b in range(100234,101234)];print(time.time()-a)
1.6594209671

Вот гораздо лучшее решение: Самый эффективный способ поиска / поиска в огромном списке (python)

Это супер быстро:

>>> from bisect import bisect_left
>>> t = list(range(0, 1000000))
>>> a=time.time();x = [t[bisect_left(t,b)]==b for b in range(100234,101234)];print(time.time()-a)
0.0054759979248