Ускорить поиск элемента в списке (через Python)

Question

У меня очень большой список, и мне нужно запустить много поисков для этого списка. Чтобы быть более конкретным, я работаю над большим текстовым файлом (> 11 Гб) для обработки, но есть элементы, которые появляются более одного раза, и я только обрабатываю их сначала, когда они появляются. Если шаблон появляется, я обрабатываю его и помещаю его в список. Если элемент появляется снова, я проверяю его в списке, и если это так, то я просто передать на обработку, например:

[...] 
if boundary.match(line): 
    if closedreg.match(logentry): 
     closedthreads.append(threadid) 
    elif threadid in closedthreads: 
     pass 
    else: 
[...] 

сам код далек от оптимального. Моя основная проблема заключается в том, что список «closedthreads» содержит несколько миллионов элементов, и вся операция только начинает замедляться и замедляться. Я думаю, что это может помочь сортировать список (или использовать объект отсортированного списка) после каждого append(), но я не уверен в этом. Какое самое элегантное решение?

Answer 1

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

closedthreads = set() 
# ... 

if boundary.match(line): 
    if closedreg.match(logentry): 
     closedthreads.add(threadid) 
    elif threadid in closedthreads: 
     pass 
    else: 

Answer 2

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

Answer 3

Нужно сохранить заказ?

Если нет - используйте комплект.

Если вы это сделаете - используйте OrderedDict. OrderedDict также позволяет хранить связанные с ним значения (например, результаты процесса)

Но ... вам нужно сохранить исходные значения вообще? Вы можете посмотреть модуль «dbm», если вы абсолютно это сделаете (или купите много памяти!) Или вместо хранения фактического текста храните SHA-1 дайджесты или что-то в этом роде. Если все, что вы хотите сделать, это убедиться, что вы не запускаете один и тот же элемент дважды, это может сработать.