Python, enorme problema de iteración de rendimiento

Question

Estoy haciendo una iteración de 3 palabras, cada una de aproximadamente 5 millones de caracteres, y quiero encontrar secuencias de 20 caracteres que identifiquen cada palabra. Es decir, quiero encontrar todas las secuencias de longitud 20 en una palabra que sea única para esa palabra. Mi problema es que el código que he escrito toma mucho tiempo para ejecutarse. Nunca he completado una sola palabra ejecutando mi programa durante la noche.

La siguiente función contiene una lista que contiene diccionarios donde cada diccionario contiene cada palabra posible de 20 y su ubicación a partir de una de las 5 millones de palabras largas.

Si alguien tiene una idea de cómo optimizar este estaría muy agradecido, no tengo ni idea de cómo continuar ...

aquí es una muestra de mi código:

def findUnique(list): 
    # Takes a list with dictionaries and compairs each element in the dictionaries 
    # with the others and puts all unique element in new dictionaries and finally 
    # puts the new dictionaries in a list. 
    # The result is a list with (in this case) 3 dictionaries containing all unique 
    # sequences and their locations from each string. 
    dicList=[] 
    listlength=len(list) 
    s=0 
    valuelist=[] 
    for i in list: 
     j=i.values() 
     valuelist.append(j) 
    while s<listlength: 
     currdic=list[s] 
     dic={} 
     for key in currdic: 
      currval=currdic[key] 
      test=True 
      n=0 
      while n<listlength: 
       if n!=s: 
        if currval in valuelist[n]: #this is where it takes to much time 
         n=listlength 
         test=False 
        else: 
         n+=1 
       else: 
        n+=1 
      if test: 
       dic[key]=currval 
     dicList.append(dic) 
     s+=1 
    return dicList 

Answer 1

def slices(seq, length, prefer_last=False): 
    unique = {} 
    if prefer_last: # this doesn't have to be a parameter, just choose one 
    for start in xrange(len(seq) - length + 1): 
     unique[seq[start:start+length]] = start 
    else: # prefer first 
    for start in xrange(len(seq) - length, -1, -1): 
     unique[seq[start:start+length]] = start 
    return unique 

# or find all locations for each slice: 
import collections 
def slices(seq, length): 
    unique = collections.defaultdict(list) 
    for start in xrange(len(seq) - length + 1): 
    unique[seq[start:start+length]].append(start) 
    return unique 

Esta función (actualmente en mi iter_util module) es O (n) (n es la longitud de cada palabra) y usaría set(slices(..)) (con operaciones de ajuste como diferencia) para obtener divisiones únicas en todas las palabras (ejemplo a continuación). También puede escribir la función para devolver un conjunto, si no desea realizar un seguimiento de las ubicaciones. El uso de memoria será alto (aunque todavía O (n), solo un factor grande), posiblemente mitigado (aunque no por mucho si la longitud es solo 20) con un "lazy slice" class especial que almacena la secuencia base (la cadena) más inicio y parada (o inicio y duración).

impresión rebanadas únicas:

a = set(slices("aab", 2)) # {"aa", "ab"} 
b = set(slices("abb", 2)) # {"ab", "bb"} 
c = set(slices("abc", 2)) # {"ab", "bc"} 
all = [a, b, c] 
import operator 
a_unique = reduce(operator.sub, (x for x in all if x is not a), a) 
print a_unique # {"aa"} 

Incluyendo lugares:

a = slices("aab", 2) 
b = slices("abb", 2) 
c = slices("abc", 2) 
all = [a, b, c] 
import operator 
a_unique = reduce(operator.sub, (set(x) for x in all if x is not a), set(a)) 
# a_unique is only the keys so far 
a_unique = dict((k, a[k]) for k in a_unique) 
# now it's a dict of slice -> location(s) 
print a_unique # {"aa": 0} or {"aa": [0]} 
       # (depending on which slices function used) 

---

En un script de prueba más cerca de sus condiciones, utilizando palabras generadas al azar de 5m caracteres y una longitud rebanada de 20 , el uso de la memoria era tan alto que mi script de prueba alcanzó rápidamente mi límite de memoria principal de 1G y comenzó a agotar la memoria virtual. En ese momento Python pasó muy poco tiempo en la CPU y lo maté. Reducir la longitud del corte o la longitud de la palabra (ya que utilicé palabras completamente aleatorias que reducen los duplicados y aumenta el uso de la memoria) para que quepan dentro de la memoria principal y funcionó por debajo de un minuto. Esta situación más O (n ** 2) en su código original tomará una eternidad, y es por eso que la complejidad algorítmica de tiempo y espacio es importante.

import operator 
import random 
import string 

def slices(seq, length): 
    unique = {} 
    for start in xrange(len(seq) - length, -1, -1): 
    unique[seq[start:start+length]] = start 
    return unique 

def sample_with_repeat(population, length, choice=random.choice): 
    return "".join(choice(population) for _ in xrange(length)) 

word_length = 5*1000*1000 
words = [sample_with_repeat(string.lowercase, word_length) for _ in xrange(3)] 
slice_length = 20 
words_slices_sets = [set(slices(x, slice_length)) for x in words] 
unique_words_slices = [reduce(operator.sub, 
           (x for x in words_slices_sets if x is not n), 
           n) 
         for n in words_slices_sets] 
print [len(x) for x in unique_words_slices] 

Answer 2

Usted dice que tiene una "palabra" 5 millones de caracteres de longitud, pero me resulta difícil de creer que esto es una palabra en el sentido habitual.

Si puede proporcionar más información acerca de sus datos de entrada, una solución específica podría estar disponible.

Por ejemplo, el texto en inglés (o cualquier otro idioma escrito) podría ser lo suficientemente repetitivo como para que un trie sea utilizable. En el peor de los casos, sin embargo, se quedaría sin memoria construyendo todas las teclas 256^20. Conocer tus aportes hace toda la diferencia.

---

edición

Me tomó un vistazo a algunos datos del genoma para ver cómo esta idea apilados, utilizando un hardcoded [ACGT] -> [0123] mapeo y 4 niños por nodo trie.

1. adenovirus 2: 35,937bp -> 35,899 distintas secuencias de 20 bases usando 469,339 nodos trie

2. enterobacterias fago lambda: 48,502bp -> 40.921 distintas secuencias de 20 bases utilizando 529.384 trie nodos.

no he tenido ningún colisiones, ya sea dentro o entre los dos conjuntos de datos, aunque tal vez hay más redundancia y/o se superponen en sus datos. Tendrás que intentarlo para ver.

Si obtiene un número útil de colisiones, podría intentar caminar las tres entradas juntas, construyendo un trie único, registrando el origen de cada hoja y eliminando colisiones del trie sobre la marcha.

Si no puede encontrar la manera de podar las teclas, puede intentar usar una representación más compacta. Por ejemplo, solo necesita 2 bits para almacenar [acgt]/[0123], lo que puede ahorrarle espacio a costa de un código un poco más complejo.

No creo que puedas simplemente forzar esto: tienes que encontrar la forma de reducir la escala del problema, y ​​eso depende del conocimiento de tu dominio.

Answer 3

Déjame construir Roger Pate's answer. Si la memoria es un problema, sugeriría que en lugar de utilizar las cadenas como las claves del diccionario, podría usar un valor hash de la cadena. Esto ahorraría el costo de almacenar la copia adicional de las cadenas como las teclas (en el peor de los casos, 20 veces el almacenamiento de una "palabra" individual).

import collections 
def hashed_slices(seq, length, hasher=None): 
    unique = collections.defaultdict(list) 
    for start in xrange(len(seq) - length + 1): 
    unique[hasher(seq[start:start+length])].append(start) 
    return unique 

(. Si realmente desea conseguir la suposición, se puede utilizar un rolling hash, aunque tendrá que cambiar la función)

Ahora, podemos combinar todos los hashes:

unique = [] # Unique words in first string 

# create a dictionary of hash values -> word index -> start position 
hashed_starts = [hashed_slices(word, 20, hashing_fcn) for word in words] 
all_hashed = collections.defaultdict(dict) 
for i, hashed in enumerate(hashed_starts) : 
    for h, starts in hashed.iteritems() : 
    # We only care about the first word 
    if h in hashed_starts[0] : 
     all_hashed[h][i]=starts 

# Now check all hashes 
for starts_by_word in all_hashed.itervalues() : 
    if len(starts_by_word) == 1 : 
    # if there's only one word for the hash, it's obviously valid 
    unique.extend(words[0][i:i+20] for i in starts_by_word.values()) 
    else : 
    # we might have a hash collision 
    candidates = {} 
    for word_idx, starts in starts_by_word.iteritems() : 
     candidates[word_idx] = set(words[word_idx][j:j+20] for j in starts) 
    # Now go that we have the candidate slices, find the unique ones 
    valid = candidates[0] 
    for word_idx, candidate_set in candidates.iteritems() : 
     if word_idx != 0 : 
     valid -= candidate_set 
    unique.extend(valid) 

(probé extendiéndola a hacer las tres cosas. es posible, pero las complicaciones podría restar valor a partir del algoritmo.)

se advirtió, no he probado esto. Además, probablemente haya muchas cosas que puede hacer para simplificar el código, pero el algoritmo tiene sentido. La parte difícil es elegir el hash. Demasiadas colisiones y no ganarás nada. Muy pocos y tendrás problemas de memoria. Si solo maneja códigos de base de ADN, puede ajustar la cadena de 20 caracteres a un número de 40 bits, y aún así no tener colisiones. Entonces las rebanadas ocuparán casi un cuarto de la memoria. Eso ahorraría aproximadamente 250 MB de memoria en la respuesta de Roger Pate.

El código sigue siendo O (N^2), pero la constante debe ser mucho menor.

Answer 4

Intento mejorar en Roger Pate's excellent answer.

En primer lugar, mantengamos conjuntos en lugar de diccionarios: de todos modos, administran la unicidad.

En segundo lugar, dado que es probable que nos quedemos sin memoria más rápido de lo que nos quedamos sin tiempo de CPU (y paciencia), podemos sacrificar la eficiencia de la CPU por la eficiencia de la memoria. Entonces quizás intente solo los 20 comenzando con una letra en particular. Para el ADN, esto reduce los requisitos en un 75%.

seqlen = 20 
maxlength = max([len(word) for word in words]) 
for startletter in letters: 
    for letterid in range(maxlength): 
     for wordid,word in words: 
      if (letterid < len(word)): 
       letter = word[letterid] 
       if letter is startletter: 
        seq = word[letterid:letterid+seqlen] 
        if seq in seqtrie and not wordid in seqtrie[seq]: 
         seqtrie[seq].append(wordid) 

O, si eso es aún demasiada memoria, podemos pasar a través de cada par posible de partida (16 pases en vez de 4 para el ADN), o cada 3 (64 pases) etc.