Более быстрое тестирование членства в python, чем set()

Мне нужно проверить наличие миллионов элементов (20-30 букв str) в списке, содержащем 10-100 тыс. этих элементов. Есть ли более быстрый способ сделать это в python, чем set()?

import sys
#load ids
ids = set( x.strip() for x in open(idfile) )

for line in sys.stdin:
    id=line.strip()
    if id in ids:
        #print fastq
        print id
        #update ids
        ids.remove( id )

Ответы

Ответ 1

set работает так же быстро, как и он.

Однако, если вы переписываете свой код для создания set один раз и не меняете его, вы можете использовать встроенный тип frozenset. Это точно так же, кроме непреложного.

Если у вас все еще есть проблемы со скоростью, вам нужно ускорить вашу программу другими способами, например, используя PyPy вместо cPython.

Ответ 2

Как я уже отмечал в своем комментарии, что, вероятно, замедлило то, что вы последовательно проверяете каждую строку из sys.stdin для членства в вашем "master". Это будет действительно, очень медленно и не позволит вам использовать скорость заданных операций. В качестве примера:

#!/usr/bin/env python

import random

# create two million-element sets of random numbers
a = set(random.sample(xrange(10000000),1000000))
b = set(random.sample(xrange(10000000),1000000))
# a intersection b
c = a & b
# a difference c
d = list(a - c) 
print "set d is all remaining elements in a not common to a intersection b"
print "length of d is %s" % len(d)

Вышеуказанное работает в ~ 6 секундах секунд на моей пятилетней машине, и оно тестирует членство в более крупных наборах, чем вам нужно (если только я не понял вас). Большая часть этого времени фактически занята созданием наборов, поэтому у вас даже не будет этих накладных расходов. Тот факт, что строки, на которые вы ссылаетесь, длинны, здесь не уместен; создание набора создает хэш-таблицу, как объясняет agf. Я подозреваю (хотя, опять же, неясно, из вашего вопроса), что если вы можете получить все свои входные данные в набор до того, как будете проходить тестирование на членство, это будет намного быстрее, в отличие от чтения его в одном элементе на время, затем проверка наличия членства

Ответ 3

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

Например, начните с простой карты, которая связывает первую букву со всеми ключами, начинающимися с этой буквы, поэтому вам не нужно искать все ключи, но только их меньшую часть.

Это будет выглядеть так:

ids = {}
for id in open(idfile):
    ids.setdefault(id[0], set()).add(id)

for line in sys.stdin:
    id=line.strip()
    if id in ids.get(id[0], set()):
       #print fastq
       print id
       #update ids
       ids[id[0]].remove( id )

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

Это первый шаг, вы можете сделать то же самое со вторым символом и т.д., поиск будет просто идти по дереву с каждой буквой...

Ответ 4

Как упоминалось urschrei, вы должны "векторизовать" чек. Быстрее проверять наличие миллиона элементов один раз (как это делается на C), чем проверять один элемент на миллион раз.