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

Question

Я должен проверить наличие миллионов элементов (20-30 букв стр.) В списке, содержащем 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 )

Answer 1

set так быстро, как он получает.

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

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

Answer 2

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

#!/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. Я подозреваю (хотя, опять же, это не ясно из вашего вопроса), что если вы сможете собрать все свои входные данные в набор до , то вы выполните какое-либо членское тестирование, это будет намного быстрее, чем чтение это по одному элементу за раз, затем проверка на членство в наборе

Answer 3

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

Answer 4

Вы должны попытаться разделить ваши данные, чтобы сделать поиск быстрее. Дерево 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 раз быстрее, если первый символ ваших ключей хорошо распределен и не всегда одинаков).

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