Python, enorme problema di prestazioni di itterazione

Question

Sto facendo un'iterazione di 3 parole, ognuna lunga circa 5 milioni di caratteri, e voglio trovare sequenze di 20 caratteri che identificano ogni parola. Cioè, voglio trovare tutte le sequenze di lunghezza 20 in una parola che è unica per quella parola. Il mio problema è che il codice che ho scritto richiede molto tempo per essere eseguito. Non ho mai nemmeno completato una sola parola sul mio programma durante la notte.

La funzione seguente accetta un elenco contenente dizionari in cui ogni dizionario contiene ciascuna parola possibile di 20 e la sua posizione da una delle 5 milioni di parole lunghe.

Se qualcuno ha un'idea su come ottimizzare questo sarei davvero grato, non ho la minima idea di come continuare ...

Ecco un esempio del mio codice:

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 

Questa funzione (attualmente nel mio iter_util module) è O (n) (n è la lunghezza di ogni parola) e usereste set(slices(..)) (con operazioni set come la differenza) per ottenere sezioni univoche su tutte le parole (esempio sotto). Puoi anche scrivere la funzione per restituire un set, se non vuoi tracciare le posizioni. L'utilizzo della memoria sarà elevato (anche se O (n), solo un grande fattore), eventualmente mitigato (sebbene non di molto se la lunghezza è solo 20) con uno speciale "lazy slice" class che memorizza la sequenza di base (la stringa) più start e stop (o inizio e lunghezza).

stampa fette uniche:

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"} 

comprese le sedi:

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) 

---

In uno script di test più vicino ai vostri condizioni, usando parole generati casualmente di 5 milioni di caratteri e una lunghezza fetta di 20 l'utilizzo della memoria è stato così elevato che il mio script di test ha raggiunto rapidamente il limite di memoria principale 1G e ha iniziato a battere la memoria virtuale. A quel punto Python ha speso molto poco tempo sulla CPU e l'ho ucciso. Ridurre la lunghezza della sezione o la lunghezza della parola (poiché ho usato parole completamente casuali che riducono i duplicati e aumenta l'uso della memoria) per adattarsi alla memoria principale e ha funzionato in meno di un minuto. Questa situazione più O (n ** 2) nel codice originale richiederà sempre, ed è per questo che la complessità algoritmica del tempo e dello spazio sono entrambi importanti.

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

Dici di avere una "parola" 5 milioni di caratteri, ma trovo difficile credere questo è una parola nel senso comune.

Se è possibile fornire ulteriori informazioni sui dati di input, potrebbe essere disponibile una soluzione specifica.

Ad esempio, il testo inglese (o qualsiasi altra lingua scritta) potrebbe essere sufficientemente ripetitivo che uno trie sarebbe utilizzabile. Nel peggiore dei casi, tuttavia, esaurirebbe la memoria costruendo tutte le chiavi 256^20. Conoscere i tuoi input fa la differenza.

---

modificare

ho preso uno sguardo ad alcuni dati del genoma per vedere come questa idea accatastati, utilizzando un hardcoded [ACGT] -> [0123] mappatura e 4 bambini per nodo trie.

1. adenovirus 2: 35,937bp -> 35,899 distinte sequenze 20-base utilizzando 469,339 nodi del trie

2. enterobatteri fago lambda: 48,502bp -> 40,921 distinte sequenze 20-base utilizzando 529.384 trie i nodi.

non ho avuto alcun collisioni, all'interno o tra i due insiemi di dati, anche se forse non v'è più la ridondanza e/o si sovrappongono nei dati. Dovresti provarlo per vedere.

Se si ottiene un numero utile di collisioni, è possibile provare a camminare insieme i tre ingressi, creando un singolo trie, registrando l'origine di ciascuna foglia e le collisioni di potatura dal trie man mano che si procede.

Se non riesci a trovare un modo per sfoltire i tasti, puoi provare a utilizzare una rappresentazione più compatta. Ad esempio, solo è necessario 2 bit per archiviare [acgt]/[0123], il che potrebbe far risparmiare spazio al costo di un codice leggermente più complesso.

Non penso che si possa solo forzare la forza bruta anche se - è necessario trovare un modo per ridurre la portata del problema, e ciò dipende dalla conoscenza del dominio.

Answer 3

Lasciami costruire Roger Pate's answer. Se la memoria è un problema, suggerirei invece di usare le stringhe come chiavi del dizionario, potresti usare un valore hash della stringa. Ciò farebbe risparmiare il costo della memorizzazione della copia extra delle stringhe come chiavi (nella peggiore delle ipotesi, 20 volte la memorizzazione di una singola "parola").

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 

(. Se davvero si vuole ottenere fantasia, è possibile utilizzare un rolling hash, anche se è necessario modificare la funzione)

Ora, siamo in grado di combinare tutti gli hash:

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) 

(ho provato estendendolo a fare tutti e tre. E 'possibile, ma le complicazioni sarebbe sminuire l'algoritmo.)

Attenzione, non ho ancora testato questo. Inoltre, c'è probabilmente molto che puoi fare per semplificare il codice, ma l'algoritmo ha senso. La parte difficile è scegliere l'hash. Troppe collisioni e non otterrai nulla. Troppo pochi e avrai problemi di memoria. Se hai a che fare solo con i codici di base del DNA, puoi inserire la stringa da 20 caratteri in un numero a 40 bit e non avere ancora collisioni. Quindi le fette occuperanno quasi un quarto della memoria. Ciò farebbe risparmiare circa 250 MB di memoria nella risposta di Roger Pate.

Il codice è ancora O (N^2), ma la costante dovrebbe essere molto più bassa.

Answer 4

Proviamo a migliorare su Roger Pate's excellent answer.

In primo luogo, manteniamo gli insiemi anziché i dizionari: gestiscono comunque l'unicità.

In secondo luogo, dal momento che è probabile che si esaurisca la memoria più velocemente di quanto si esaurisca il tempo della CPU (e la pazienza), possiamo sacrificare l'efficienza della CPU per motivi di efficienza della memoria. Quindi forse prova solo gli anni '20 che iniziano con una lettera particolare. Per il DNA, questo riduce i requisiti del 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) 

Oppure, se questo è ancora troppa memoria, siamo in grado di passare attraverso per ogni possibile coppia di partenza (16 passaggi invece di 4 per il DNA), o ogni 3 (64 passaggi) ecc