Effiziente String-Verkettung

[epsilon]

Ich hab hier 'ne interessante Seite gefunden, auf der jemand verschiedene Methoden verglichen hat Strings zu verketten:

http://www.skymind.com/~ocrow/python_string/

Der Test ist allerdings schon etwas älter und es wird deshalb Python 2.2.1 verwendet. Weiß jemand, ob sich seit dem etwas verändert hat bzw. ob irgendeine weitere Methode dazu gekommen ist?

[Leonidas]

Letztendlich ist Methode 4 und 6 genau das gleiche. Die Unterschiede die der Autor da misst kommen nicht von der Konkatenation, denn die ist die gleiche sondern von der ``for``-Schleife bzw der LC. Methode sieben könnte sein, dass man die LC zu einer Generator Expression macht, also die eckigen Klammern weglässt und nachschaut was dann passiert.

Noch dazu glaube ich mich zu erinnern, dass die naive Konkatenation auch irgendwann von der Laufzeit her verbessert wurde - aber man sollte es dennoch nicht so machen.

[epsilon]

Noch dazu glaube ich mich zu erinnern, dass die naive Konkatenation auch irgendwann von der Laufzeit her verbessert wurde - aber man sollte es dennoch nicht so machen.

Ich hab' das jetzt mal getestet:

Code: Alles auswählen

#!/usr/bin/env python
# -*- coding: utf-8 -*-

from time import time

def f():
    start = time()
    x=[]
    for i in xrange(10000000):
        x.append(str(i))
    s = ''.join(x)
    return time() - start

def f2():
    start = time()
    x=''
    for i in xrange(10000000):
        x += str(i)
    return time() - start

print "Creating string with list.join: %s" % f()
print "Creating string with append: %s" % f2()

Ausgabe:

Creating string with list.join: 11.873000145
Creating string with append: 9.56592392921

Kann das mal jemand gegen testen?

[BlackJack]

Hier drei Läufe mit Python 2.5:

Creating string with list.join: 10.153055191
Creating string with append: 10.0147440434

Creating string with list.join: 9.77350783348
Creating string with append: 10.6794538498

Creating string with list.join: 10.1968660355
Creating string with append: 10.2206950188

Deine erste Variante verbrennt unnötig Zeit in der Schleife. Die Erzeugung der Daten würde ich grundsätzlich nicht mit messen.

Ausserdem muss man aufpassen welche Python-Implementierung man verwendet, denn `+=` auf Zeichenketten, auf die es nur eine einzige Referenz gibt, wurde in CPython, ich glaube ab 2.4 optimiert. Solche Zeichenketten werden dabei nämlich nicht mehr als "immutable" betrachtet und wenn möglich "in place" erweitert. Merkt ja keiner.

[lunar]

Rohdaten
Messkript

Allerdings sollte man trotz der Effizienz einer direkten Konkatenation unter CPython immer daran denken, dass IronPython and Jython diese Konkatenation afaik sehr ineffizient durchführen.

[epsilon]

Du hast Recht. Ich generiere die Daten jetzt vor den Tests und habe noch zwei Funktionen hinzugefügt die eher das machen, was ich später auch wirklich verwende:

http://nopaste.info/f2b8d77079.html

Ausserdem muss man aufpassen welche Python-Implementierung man verwendet, denn `+=` auf Zeichenketten, auf die es nur eine einzige Referenz gibt, wurde in CPython, ich glaube ab 2.4 optimiert. Solche Zeichenketten werden dabei nämlich nicht mehr als "immutable" betrachtet und wenn möglich "in place" erweitert. Merkt ja keiner.

Ich verwende Python 2.5.2.

Bei f3 sollten ja jetzt 2 Referenzen auf das string Objekt existieren, richtig?

Ergebnis:

f1: 0.692623138428 - str.join(list)
f2: 0.343039989471 - str += str
f3: 0.316588878632 - str += str
f4: 1.20108604431 - str.join(list)
f5: 0.8058989048 - str += str

f1: 0.696048974991
f2: 0.351753950119
f3: 0.323728084564
f4: 1.20475101471
f5: 0.81294298172

f1: 0.714812040329
f2: 0.34762096405
f3: 0.330101966858
f4: 1.21382403374
f5: 0.81110906601

Merkwürdig.

lunar, du hättest noch dazu schreiben können, dass du die string-Verkettung mit einem for-loop gemacht hast, bzw. hättest die string-Verkettung noch mit einer list comprehension testen können. Ansonsten ist das ja eher so, als ob man Äpfel und Birnen vergleicht, wenn man das Ergebnis von str.join(list) und list comprehension mit dem Ergebnis von str += str und for-loop vergleicht.

[lunar]

lunar, du hättest noch dazu schreiben können, dass du die string-Verkettung mit einem for-loop gemacht hast, bzw. hättest die string-Verkettung noch mit einer list comprehension testen können.

Wie das? Zuweisung sind in einer LC nicht möglich.

Ansonsten ist das ja eher so, als ob man Äpfel und Birnen vergleicht, wenn man das Ergebnis von str.join(list) und list comprehension mit dem Ergebnis von str += str und for-loop vergleicht.

Es ist imho nicht die Schleife als solches, sondern der wiederholte "append()"-Aufruf, der der ".join()"-Variante die Geschwindigkeit kostet. Dieser Aufruf entfällt ja beim Konkatenieren.

[epsilon]

lunar, du hättest noch dazu schreiben können, dass du die string-Verkettung mit einem for-loop gemacht hast, bzw. hättest die string-Verkettung noch mit einer list comprehension testen können.

Wie das? Zuweisung sind in einer LC nicht möglich.

Oh, stimmt, dran hatte ich gar nicht gedacht

Ansonsten ist das ja eher so, als ob man Äpfel und Birnen vergleicht, wenn man das Ergebnis von str.join(list) und list comprehension mit dem Ergebnis von str += str und for-loop vergleicht.

Es ist imho nicht die Schleife als solches, sondern der wiederholte "append()"-Aufruf, der der ".join()"-Variante die Geschwindigkeit kostet. Dieser Aufruf entfällt ja beim Konkatenieren.

Ich meinte damit, dass list comprehension wesentlich effizienter ist, als ein for-loop. Und es dadurch "unfair" wäre, wenn man das eine, was list comprehension verwendet, mit dem andern, was einen for-loop verwendet, vergleicht.

Aber wenn list comprehension mit dem einen nicht (ohne weiteres) möglich ist, kann man wohl nichts machen.

[lunar]

Ansonsten ist das ja eher so, als ob man Äpfel und Birnen vergleicht, wenn man das Ergebnis von str.join(list) und list comprehension mit dem Ergebnis von str += str und for-loop vergleicht.

Es ist imho nicht die Schleife als solches, sondern der wiederholte "append()"-Aufruf, der der ".join()"-Variante die Geschwindigkeit kostet. Dieser Aufruf entfällt ja beim Konkatenieren.

Ich meinte damit, dass list comprehension wesentlich effizienter ist, als ein for-loop. Und es dadurch "unfair" wäre, wenn man das eine, was list comprehension verwendet, mit dem andern, was einen for-loop verwendet, vergleicht.

Ich glaube nicht, dass eine LC per se effizienter ist als eine Vorschleife. Ansonsten wäre es erstaunlich, dass for-Schleife + Konkatenation schneller ist als ''.join() und LC. Ich denke mal, es ist die Erzeugung der Liste per .append(), die der Performance kostet. Insofern glaube ich, dass eine Konkatenation innerhalb einer LC sogar langsamer wäre, da ja völlig umsonst eine Liste erzeugt wird. Ist aber nur meine Ansicht, mit den Python-Interna kenne ich mich nicht so gut aus.

[Y0Gi]

Ich gehe davon aus, dass eine LC effizienter arbeitet als sie mit einem `for`-Loop und `list.append()` funktionell zu emulieren. Möglicherweise/hoffentlich sind LCs intern so optimiert, dass gar kein richtiger Call pro hinzuzufügendem Element erforderlich ist.

"Interna-Spezis, bitte die vier, Interna-Spezis bitte"

[BlackJack]

Interna? Bitteschön:

Code: Alles auswählen

In [111]: def f(xs):
   .....:     result = []
   .....:     for x in xs:
   .....:         result.append(x)
   .....:

In [112]: def g(xs):
   .....:     [x for x in xs]
   .....:

In [113]: import dis

In [114]: dis.dis(f)
  2           0 BUILD_LIST               0
              3 STORE_FAST               1 (result)

  3           6 SETUP_LOOP              27 (to 36)
              9 LOAD_FAST                0 (xs)
             12 GET_ITER
        >>   13 FOR_ITER                19 (to 35)
             16 STORE_FAST               2 (x)

  4          19 LOAD_FAST                1 (result)
             22 LOAD_ATTR                0 (append)
             25 LOAD_FAST                2 (x)
             28 CALL_FUNCTION            1
             31 POP_TOP
             32 JUMP_ABSOLUTE           13
        >>   35 POP_BLOCK
        >>   36 LOAD_CONST               0 (None)
             39 RETURN_VALUE

In [115]: dis.dis(g)
  2           0 BUILD_LIST               0
              3 DUP_TOP
              4 STORE_FAST               1 (_[1])
              7 LOAD_FAST                0 (xs)
             10 GET_ITER
        >>   11 FOR_ITER                13 (to 27)
             14 STORE_FAST               2 (x)
             17 LOAD_FAST                1 (_[1])
             20 LOAD_FAST                2 (x)
             23 LIST_APPEND
             24 JUMP_ABSOLUTE           11
        >>   27 DELETE_FAST              1 (_[1])
             30 POP_TOP
             31 LOAD_CONST               0 (None)
             34 RETURN_VALUE

Der Hauptunterschied ist in der Tat, dass bei der LC intern ein Bytecodebefehl ``LIST_APPEND`` ausgeführt wird, während bei der Schleife bei jedem Durchlauf das `append` Attribut vom Objekt abgefragt und dann aufgerufen wird.

[epsilon]

Ich glaube nicht, dass eine LC per se effizienter ist als eine Vorschleife.

strange. Ich dachte mehrfach gelesen zu haben, dass LC immer schneller wäre als ein for-loop. In Wirklichkeit ist LC sogar langsamer, wenn ich keine Liste erzeugen will:

Code: Alles auswählen

from time import time

l = xrange(10000000)

def f1():
    start = time()
    for x in l:
        None
    return time() - start

def f2():
    start = time()
    [None for x in l]
    return time() - start
    
print "f1: %s" % f1()
print "f2: %s" % f2()

f1: 0.927053928375
f2: 1.2819519043

f1: 1.1031961441
f2: 1.4633500576

f1: 0.955038070679
f2: 1.30906295776

[Leonidas]

In Wirklichkeit ist LC sogar langsamer, wenn ich keine Liste erzeugen will

Natürlich. Schneller ist sie nur, da sie keine Lookups für das ``append`` braucht, ohne das ``append`` ist die for-Schleife schneller, eben weil gar keine Liste erzeugt wird (also insgesamt weniger gemacht wird).

[epsilon]

Bisher habe ich LC nähmlich auch verwendet, wenn ich eine Funktion x mal aufrufen musste...

Was mich noch interessiert, @ Leonidas: du hattest ja das hier geschrieben:

Noch dazu glaube ich mich zu erinnern, dass die naive Konkatenation auch irgendwann von der Laufzeit her verbessert wurde - aber man sollte es dennoch nicht so machen.

Was genau hast damit denn gemeint?

[Leonidas]

Bisher habe ich LC nähmlich auch verwendet, wenn ich eine Funktion x mal aufrufen musste...

Ist aber auch stilistisch blöd. Man sollte eine LC wirklich nur nutzen, wenn man die Rückgabewerte auch wirklich braucht und sie nicht dazu verwenden eine Liste von None auszugeben.

Was genau hast damit denn gemeint?

Ich habe damit gemeint, dass trotz der Verbesserungen in CPython ``''.join()`` dennoch bevorzugt werden sollte.

[lunar]

Er hat wohl gemeint, dass String-Konkatenation in anderen Python-Implementierung wie Jython und IronPython wesentlich ineffizienter ist.

CPython implementiert effiziente String-Konkatenation offenbar, in dem es die Unveränderbarkeit von Strings aufhebt.

Die String-Typen der CLR und der JVM dagegen sind völlig unveränderbar, so dass ein solcher Trick nicht funktioniert. Stattdessen verlassen sich IronPython und Jython da wohl auf die Konkatenation der darunter liegenden Plattform, und die ist eben ineffizient. ''.join() dagegen kann effizient implementiert werden, beispielsweise mit der StringBuilder-Klasse der JVM.

[Leonidas]

CPython implementiert effiziente String-Konkatenation offenbar, in dem es die Unveränderbarkeit von Strings aufhebt.

Ja, nehme ich an. Aber spätestens wenn es mehrere Referenzen auf ein String-Objekt gibt, geht das nicht mehr so einfach.

[epsilon]

Was genau hast damit denn gemeint?

Ich habe damit gemeint, dass trotz der Verbesserungen in CPython ``''.join()`` dennoch bevorzugt werden sollte.

Ich wollte eher den Grund dafür wissen, warum ich trotzdem ''.join() verwenden soll
Gibt es neben dem von lunar genannten Grund, einen weiteren Grund ''.join() zu verwenden?

CPython implementiert effiziente String-Konkatenation offenbar, in dem es die Unveränderbarkeit von Strings aufhebt.

Ja, nehme ich an. Aber spätestens wenn es mehrere Referenzen auf ein String-Objekt gibt, geht das nicht mehr so einfach.

Wenn ich das hier schreibe:
x = 'foo'
y = x
z = y
existieren 3 Referenzen auf 'foo', richtig? Wenn ja, sollten Referenzen keinen Unterschied machen:

Code: Alles auswählen

from time import time

l = [str(x) for x in xrange(10000000)]

def f1():
    start = time()
    x=''
    for n in l:
        x += n
    return time() - start


def f2():
    start = time()
    x = ''
    y = x
    z = y
    for n in l:
        x += n
    return time() - start

print "f1: %s" % f1()
print "f2: %s" % f2()

f1: 2.07027602196
f2: 1.91980409622

f1: 1.98824310303
f2: 2.04973912239

f1: 1.96024012566
f2: 1.91407608986

[BlackJack]

Ja und nein. Referenzen machen einen Unterschied, aber nach dem ersten Schleifendurchlauf wird `x` an eine neue Zeichenkette gebunden zu der (höchstwahrscheinlich) `x` die einzige Referenz ist.

Aber die Optimierung greift halt nur unter CPython ab Version 2.4 und deshalb sollte man sich nicht darauf verlassen, dass das wirklich überall so funktioniert. Ich würde das jetzt auch nicht an irgend welchen Mikrobenchmarks festmachen, sondern daran, dass wiederholtes ``+=`` mit unveränderbaren Zeichenketten quadratische Laufzeit hat, während `join()` mit linearer Laufzeit implementiert werden kann.