Когда вы делаете что-то вроде "test" in a, где a - это список, выполняемый python, выполняет последовательный поиск в списке или создает ли представление хэш-таблицы для оптимизации поиска? В приложении мне это нужно, потому что я буду делать много поисков в списке, так что было бы лучше сделать что-то вроде b = set(a), а затем "test" in b? Также обратите внимание, что список значений, которые у меня будут, не будет иметь повторяющихся данных, и я действительно не забочусь о его заказе; Мне просто нужно проверить наличие значения.
Также обратите внимание, что список значений, которые у меня будут, не будет иметь повторяющихся данных, и я действительно не забочусь о его заказе; Мне просто нужно проверить наличие значения.
Не используйте список, вместо этого используйте set(). Он имеет именно те свойства, которые вы хотите, включая быстрый тест in.
Я видел ускорения в 20 раз и выше в местах (в основном тяжелый хруст числа), где один список был изменен для набора.
"test" in a со списком a выполнит линейный поиск. Настройка хеш-таблицы на лету будет намного дороже, чем линейный поиск. "test" in b, с другой стороны, сделает анимированный O (1) хэш-поиск.
В описанном вами случае не существует причины использовать список по набору.
Я думаю, что было бы лучше пойти с установленной реализацией. Я знаю, что наборы имеют O (1) время поиска. Я думаю, что списки берут O (n) время поиска. Но даже если списки также относятся к O (1), вы ничего не теряете при переключении на наборы.
Кроме того, в наборах не допускаются повторяющиеся значения. Это также сделает вашу программу более эффективной с точки зрения памяти.
Список и кортежи, похоже, имеют одно и то же время, а использование "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