pruebas de membresía más rápidas en python que set()

performance fastq

Question

Tengo que verificar la presencia de millones de elementos (20-30 letras str) en la lista que contiene 10-100k de esos elementos. ¿Hay una forma más rápida de hacerlo en python que 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

Como lo mencionó urschrei, debe "vectorizar" el cheque. Es más rápido verificar la presencia de un millón de elementos una vez (como se hace en C) que hacer la comprobación de un elemento un millón de veces.

Answer 2

Como señalé en mi comentario, lo que probablemente te está ralentizando es que estás verificando secuencialmente cada línea de sys.stdin para determinar la membresía de tu conjunto "maestro". Esto va a ser muy, muy lento, y no le permite hacer uso de la velocidad de las operaciones de configuración. Como ejemplo:

#!/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)

Lo anterior se ejecuta en ~ 6 segundos de reloj de pared en mi máquina de cinco años, y está probando la membresía en conjuntos más grandes de los que necesita (a menos que lo haya entendido mal). La mayoría de ese tiempo se dedica a crear los conjuntos, por lo que ni siquiera tendrá esa sobrecarga. El hecho de que las cadenas a las que te refieres sean largas no es relevante aquí; la creación de un conjunto crea una tabla hash, como se explica en AGF. Sospecho (aunque de nuevo, no queda claro en su pregunta) que si puede obtener todos sus datos de entrada en un conjunto antes de realizar cualquier prueba de membresía, será mucho más rápido, en lugar de leerlo en un elemento a un tiempo, luego comprobando el conjunto de miembros

Answer 3

Debes intentar dividir tus datos para que la búsqueda sea más rápida. La estructura de árbol le permitirá encontrar muy rápidamente si los datos están presentes o no.

Por ejemplo, comience con un mapa simple que vincule la primera letra con todas las teclas que comienzan con esa letra, por lo que no tiene que buscar todas las teclas, sino solo una parte más pequeña de ellas.

Esto se vería como:

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 )

La creación será un poco más lenta, pero la búsqueda debería ser mucho más rápida (esperaría 20 veces más rápido, si el primer carácter de sus claves está bien distribuido y no siempre es el mismo).

Este es un primer paso, usted podría hacer lo mismo con el segundo personaje y así sucesivamente, la búsqueda sería simplemente caminar el árbol con cada letra ...

Answer 4

set es tan rápido como se pone.

Sin embargo, si reescribe su código para crear el set una vez, y no lo cambia, puede usar el tipo incorporado frozenset . Es exactamente lo mismo excepto inmutable.

Si aún tiene problemas de velocidad, debe acelerar su programa de otras maneras, como usar PyPy lugar de cPython.