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?
Effiziente String-Verkettung
-
- Python-Forum Veteran
- Beiträge: 16025
- Registriert: Freitag 20. Juni 2003, 16:30
- Kontaktdaten:
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.
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.
My god, it's full of CARs! | Leonidasvoice vs (former) Modvoice
Ich hab' das jetzt mal getestet:Leonidas hat 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.
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()
Creating string with list.join: 11.873000145
Creating string with append: 9.56592392921
Kann das mal jemand gegen testen?
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.
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.
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
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.
http://nopaste.info/f2b8d77079.html
Ich verwende Python 2.5.2.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.
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.
Wie das? Zuweisung sind in einer LC nicht möglich.epsilon hat geschrieben: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.
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.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.
Oh, stimmt, dran hatte ich gar nicht gedachtlunar hat geschrieben:Wie das? Zuweisung sind in einer LC nicht möglich.epsilon hat geschrieben: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.
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.lunar hat geschrieben: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.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.
Aber wenn list comprehension mit dem einen nicht (ohne weiteres) möglich ist, kann man wohl nichts machen.
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.epsilon hat geschrieben: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.lunar hat geschrieben: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.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.
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"
"Interna-Spezis, bitte die vier, Interna-Spezis bitte"
Interna? Bitteschön:
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.
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
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:Ich glaube nicht, dass eine LC per se effizienter ist als eine Vorschleife.
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()
f2: 1.2819519043
f1: 1.1031961441
f2: 1.4633500576
f1: 0.955038070679
f2: 1.30906295776
-
- Python-Forum Veteran
- Beiträge: 16025
- Registriert: Freitag 20. Juni 2003, 16:30
- Kontaktdaten:
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 hat geschrieben:In Wirklichkeit ist LC sogar langsamer, wenn ich keine Liste erzeugen will
My god, it's full of CARs! | Leonidasvoice vs (former) Modvoice
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:
Was mich noch interessiert, @ Leonidas: du hattest ja das hier geschrieben:
Was genau hast damit denn gemeint?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.
-
- Python-Forum Veteran
- Beiträge: 16025
- Registriert: Freitag 20. Juni 2003, 16:30
- Kontaktdaten:
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.epsilon hat geschrieben:Bisher habe ich LC nähmlich auch verwendet, wenn ich eine Funktion x mal aufrufen musste...
Ich habe damit gemeint, dass trotz der Verbesserungen in CPython ``''.join()`` dennoch bevorzugt werden sollte.epsilon hat geschrieben:Was genau hast damit denn gemeint?
My god, it's full of CARs! | Leonidasvoice vs (former) Modvoice
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.
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.
-
- Python-Forum Veteran
- Beiträge: 16025
- Registriert: Freitag 20. Juni 2003, 16:30
- Kontaktdaten:
Ja, nehme ich an. Aber spätestens wenn es mehrere Referenzen auf ein String-Objekt gibt, geht das nicht mehr so einfach.lunar hat geschrieben:CPython implementiert effiziente String-Konkatenation offenbar, in dem es die Unveränderbarkeit von Strings aufhebt.
My god, it's full of CARs! | Leonidasvoice vs (former) Modvoice
Ich wollte eher den Grund dafür wissen, warum ich trotzdem ''.join() verwenden sollLeonidas hat geschrieben:Ich habe damit gemeint, dass trotz der Verbesserungen in CPython ``''.join()`` dennoch bevorzugt werden sollte.epsilon hat geschrieben:Was genau hast damit denn gemeint?
Gibt es neben dem von lunar genannten Grund, einen weiteren Grund ''.join() zu verwenden?
Wenn ich das hier schreibe:Leonidas hat geschrieben:Ja, nehme ich an. Aber spätestens wenn es mehrere Referenzen auf ein String-Objekt gibt, geht das nicht mehr so einfach.lunar hat geschrieben:CPython implementiert effiziente String-Konkatenation offenbar, in dem es die Unveränderbarkeit von Strings aufhebt.
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
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.
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.