Fäden verbinden. Generator oder Listenverständnis?

Question

Betrachten Sie das Problem der Alphabete aus einer großen Zeichenfolge extrahieren.

Eine Möglichkeit ist, zu tun

''.join([c for c in hugestring if c.isalpha()]) 

Der Mechanismus ist klar: Die Liste Verständnis eine Liste von Zeichen erzeugt. Die Join-Methode weiß, wie viele Zeichen benötigt werden, um auf die Länge der Liste zuzugreifen.

Andere Art und Weise zu tun, ist

''.join(c for c in hugestring if c.isalpha()) 

Hier wird der Generator Verständnis führt zu einem Generator. Die Join-Methode weiß nicht, wie viele Zeichen sie verbinden wird, da der Generator kein len Attribut besitzt. Diese Art des Beitritts sollte also langsamer sein als die Listenverständnismethode.

Testen in Python zeigt jedoch, dass es nicht langsamer ist. Warum ist das so? Kann jemand erklären, wie Join an einem Generator funktioniert.

Um klar zu sein:

sum(j for j in range(100)) 

benötigt keine Kenntnisse von 100 zu haben, weil sie den Überblick über die kumulative Summe zu halten. Er kann auf das nächste Element zugreifen, indem er die nächste Methode für den Generator verwendet, und dann zur kumulativen Summe hinzufügen. Da Strings jedoch unveränderlich sind, würde das kumulative Verknüpfen von Strings in jeder Iteration eine neue Zeichenfolge erzeugen. Das würde also viel Zeit in Anspruch nehmen.

Answer 1

Wenn Sie rufen str.join(gen), wo gen ist ein Generator, Python macht das Äquivalent von list(gen), bevor Sie weitergehen, um die Länge der resultierenden Sequenz zu untersuchen.

Insbesondere wenn Sie look at the code implementing str.join in CPython, werden Sie diesen Anruf sehen:

fseq = PySequence_Fast(seq, "can only join an iterable"); 

Der Aufruf von PySequence_Fast wandelt das seq Argument in eine Liste, wenn es bereits nicht eine Liste oder Tupel war.

So werden die beiden Versionen Ihres Anrufs fast identisch behandelt. Im Listenverständnis erstellen Sie die Liste selbst und übergeben sie an join. In der Generatorausdruckversion wird das übergebene Generatorobjekt direkt zu Beginn list in join umgewandelt und der Rest des Codes funktioniert für beide Versionen gleich.

Answer 2

join() muss nicht als sequenzielles Anhängen von Elementen der Sequenz an eine längere und längere akkumulierte Zeichenfolge implementiert werden (was bei langen Sequenzen in der Tat sehr langsam wäre); es muss nur das gleiche Ergebnis erzielen. So join() ist wahrscheinlich nur an einen internen Speicherpuffer Zeichen anfügen und am Ende eine Zeichenfolge daraus erstellen. Das Listenverständniskonstrukt hingegen muss zuerst die Liste konstruieren (indem es den Generator hugestring durchquert) und erst dann seine Arbeit beginnen lassen.

Auch bezweifle ich, dass join() auf die Länge der Liste schaut, da es nicht wissen kann, dass jedes Element ein einzelnes Zeichen ist (in den meisten Fällen wird es nicht sein) - es erhält wahrscheinlich nur einen Generator aus der Liste .

Answer 3

Zumindest auf meiner Maschine ist das Listenverständnis für den Fall, den ich getestet habe, schneller, wahrscheinlich aufgrund ''.join in der Lage, die Speicherzuweisung zu optimieren. Es ist wahrscheinlich nur darauf an, das spezifische Beispiel Sie testen (zB wenn die Bedingung Sie testen weniger häufig auftritt, zahlt der Preis CPython für nicht Länge voraus zu wissen, kann kleiner sein):

In [18]: s = ''.join(np.random.choice(list(string.printable), 1000000)) 

In [19]: %timeit ''.join(c for c in s if c.isalpha()) 
10 loops, best of 3: 69.1 ms per loop 

In [20]: %timeit ''.join([c for c in s if c.isalpha()]) 
10 loops, best of 3: 61.8 ms per loop