explodierenden Speicher Usuing Permutationen von itertools

Question

Ich benutze Permutationen von Itertools, um eine Liste von möglichen Kombinationen einer Liste von Satz Chunks zu machen, aber es scheint den Speicher sogar auf meinem 64GB-Maschine sehr schnell explodieren. Ich bin nicht der Beste, wenn es um Speicherverwaltung geht, also würde ich gerne lernen, wie ich meinen Code verbessern kann. Wenn ich eine Liste von mehreren tausend dieser Brocken berechnen könnte, wäre das großartig. Im Moment kann ich nur wirklich 10.

import itertools 
from os import sys 

arq_in = sys.argv[1] 
f1 = open(arq_in, 'r') 

list_items = [] 
items = [] 

lines = f1.readlines() 
for line in lines: 
    line =line.strip() 
    list_items.append(line) 

for L in range(0, len(list_items)+1): 
    for subset in itertools.permutations(list_items, L): 
     items.append(subset) 

output = "\n".join(" ".join(map(str,l)) for l in items) 
print output 

leisten hier ist meine Eingabe:

ah k l ih r ih ng hh w ae r 
ah s eh k ih n d t w ih ch t 
ah s iy k r ih t w ah r l d 
ah s l iy p ih ng k ae p s l 
ah v ay t ah m ah n ae n d 
d aw n ih n b ih k ah r ih ng 
d ey t ah p oy n t s ih n 
ey jh ih n s iy hh ay ah r d ah 
f ih ng g ah r hh ae d ah 
ih g z ih s t ih n w ao r m 
ih k s p r eh sh ih n ih n dh ah 
ih n d ah l jh ih n ae n 
ih n m ay ey jh ih n s iy 
ih n v eh s t ih n b l ae k 
ih z m eh zh ah r d ih n 
m ae ch ih ng y aa r n ih n 
r iy d ih ng ih n p uh r 
s ah ch ah d ih z ae s t ah r 
s ih s t ah m ae n d ae d 
th r eh d m ae ch ih ng y aa r n 

Answer 1

Wenn Sie es auf die folgende Weise ausführen, stellen Sie sicher, dass Ihnen nicht zu wenig Speicher zur Verfügung steht, da wir eine faule Auswertung verwenden (dh wir berechnen die nächste Iteration nur, wenn wir sie benötigen).

Dieser Ansatz hat den Vorteil, nicht die ganze Sache im Speicher zu halten, so dass, obwohl es nach wie vor für eine sehr lange Zeit läuft, bis es fertig ist (es läuft über eine Stunde auf meiner Maschine und hat immer noch nicht fertig), aber es wird nicht abstürzen:

import itertools 
from os import sys 

def lazy_iter(lines): 
    list_items = [] 
    for line in lines: 
     line =line.strip() 
     list_items.append(line) 

    for L in range(0, len(list_items)+1): 
     for subset in itertools.permutations(list_items, L): 
      yield subset 


if __name__ == "__main__": 
    arq_in = sys.argv[1] 
    f1 = open(arq_in, 'r') 
    lines = f1.readlines()  
    for l in lazy_iter(lines): 
     print map(str,l) 

Unter der Annahme, wollen Sie nicht wirklich eine solche l als String print, können Sie die Wiederholungen beschränken nur für die Anzahl der Artikel, die Sie generieren möchten laufen und mache mit jedem von ihnen was immer du brauchst.

Answer 2

Wie @BrenBarn weist darauf hin, gibt es viele Permutationen für noch relativ kleine Listen. In der Tat, für eine Liste von n Artikel, von denen Sie i Artikel wählen, gibt es n!/((i!) (i-1)!) Permutationen. Wenn Sie sich jedoch die Verarbeitungszeit leisten können (die Sie benötigen, um die Liste vollständig zu verarbeiten), können Sie anstatt den gesamten Satz von Permutationen auf einmal zu verarbeiten, eine generator, wie itertools, inkrementell erstellen bis dein Endergebnis.