Warum Join ist schneller als normale Verkettung

Question

Ich habe mehrere Beispiele aus verschiedenen Sprachen gesehen, die eindeutig beweisen, dass das Verbinden von Elementen einer Liste (Array) mal schneller ist als das Verketten von Strings. Leider habe ich keine Erklärung gefunden warum? Kann jemand den inneren Algorithmus erklären, der unter beiden Operationen funktioniert und warum der eine schneller ist als der andere?

Dies ist ein Python-Beispiel dafür, was ich meine:

# This is slow 
x = 'a' 
x += 'b' 
... 
x += 'z' 

# This is fast 
x = ['a', 'b', ... 'z'] 
x = ''.join(x) 

Dank ist vorher)

Answer 1

Der Code in einer Join-Funktion kennt alle Strings, deren Verkettung gefragt wird, und wie groß diese Strings sind, daher kann er die endgültige String-Länge vor Beginn der Operation berechnen. Daher muss es nur einmal Speicher für die endgültige Zeichenfolge zuweisen und dann kann es jede Quellzeichenfolge (und Trennzeichen) an der richtigen Stelle im Speicher platzieren.

Auf der anderen Seite hat eine einzelne + = Operation auf einem String keine andere Wahl, als einfach genug Speicher für den letzten String zuzuweisen, der die Verkettung von nur zwei Strings darstellt. Nachfolgendes + = muss dasselbe tun, jeder Speicher, der auf dem nächsten + = verworfen wird. Jedes Mal, wenn die ständig wachsende Zeichenfolge von einem Speicherplatz in einen anderen kopiert wird.

Answer 2

Nun, das stark sprachabhängig ist, aber die Idee, es in der Regel ist, dass eine große Operation ist schneller als viele kleine. In Ihrem zweiten Beispiel kennt der Join alle Elemente, denen er beitreten muss, und kann daher einfach die erforderlichen Ressourcen zuweisen und die Zeichen einfügen. Die Verkettung in Ihrem ersten Beispiel muss Ressourcen in jedem einzelnen Schritt neu zuweisen (Worst-Case). Diese

Answer 3

ist, weil ein immer größerer Teil des Speichers hat für die String-Verkettung zugewiesen werden:

x = 'a' # String of size 1 allocated 
x += 'b' # String of size 2 allocated, x copied, and 'b' added. Old x discarded 
x += 'b' # String of size 3 allocated, x copied, and 'c' added. Old x discarded 
x += 'b' # String of size 4 allocated, x copied, and 'd' added. Old x discarded 
x += 'b' # String of size 5 allocated, x copied, and 'e' added. Old x discarded 

Also, was passiert, ist, Sie führen große Zuweisungen und Kopien, aber dann umdrehen und werfen sie weg. Sehr verschwenderisch.

x = ['a', 'b', ..., 'z'] # 26 small allocations 
x = ''.join(x) # A single, large allocation 

Answer 4

Ich weiß nicht, die Interna zu verbinden, aber in der ersten Version erstellen Sie eine neue Zeichenfolge jedes Mal wenn Sie den Operator + = nennen. Da Strings unveränderbar sind, jedes Mal, wenn neuer Speicher zugewiesen wird und eine Kopie erstellt wird.

Jetzt kann der Join (der eine String-Methode ist) nur eine einzige Zuweisung vornehmen, da er die Größe vorher berechnen kann.

Answer 5

Der Grund ist, dass Zeichenfolgen in Python (und vielen anderen Sprachen) immutable objects sind - das heißt, einmal erstellt, können sie nicht geändert werden. Bei der Verkettung einer Zeichenfolge wird stattdessen eine neue Zeichenfolge erstellt, die aus den Inhalten der beiden kleineren verketteten Zeichenfolgen besteht, und dann die alte Zeichenfolge durch die neue Zeichenfolge ersetzt.

Da das Erstellen eines Strings eine gewisse Zeit in Anspruch nimmt (Speicher reservieren, den Inhalt des Strings in den Speicher kopieren usw.), dauert es länger als eine einzige Zeichenkette. Doing N Verkettungen erfordert N neue Strings in dem Prozess zu erstellen. join(), auf der anderen Seite, muss nur eine einzige Zeichenfolge (das Endergebnis) erstellen und funktioniert daher viel schneller.

Answer 6

Siehe python string join performance und eine spezifische anwser, dass es sehr gut beschreibt:

Der Rat ist über eine Menge von Strings verketten.

berechnen s = s1 + s2 + ... + sn,

1) + verwenden. Eine neue Zeichenkette s1 + s2 wird erzeugt, dann wird eine neue Zeichenkette s1 + s2 + s3 erzeugt, ..., usw., so daß eine Menge Speicherzuweisungs- und Kopieroperationen beteiligt sind. Tatsächlich wird s1 n-1 mal kopiert, s2 wird n-2 mal kopiert, ..., usw.

2) benutze "" .join ([s1, s2, ..., sn]). Die Verkettung erfolgt in einem Durchgang und jedes Zeichen in den Strings wird nur einmal kopiert.

Answer 7

Die anderen Antworten haben es im Grunde bedeckt, aber wenn Sie noch mehr Details wollen, hat Joel Spolsky einen Artikel, in dem er „Schlemiel the painter's algorithm“ beschreibt, die äußerst relevant ist und macht schön den Fall dafür, warum das Verständnis dieser Art von Low Level-Implementierungsdetails sind immer noch sehr wichtig, selbst wenn Sie in einer höheren Programmiersprache wie Python arbeiten.