Effiziente String-Verkettung

Gute Links und Tutorials könnt ihr hier posten.
lunar

Freitag 3. Oktober 2008, 21:46

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
Administrator
Beiträge: 16024
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Freitag 3. Oktober 2008, 21:48

lunar hat geschrieben: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.
My god, it's full of CARs! | Leonidasvoice vs Modvoice
epsilon
User
Beiträge: 71
Registriert: Freitag 20. Juni 2008, 19:48

Freitag 3. Oktober 2008, 23:09

Leonidas hat geschrieben:
epsilon hat geschrieben: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 :lol:
Gibt es neben dem von lunar genannten Grund, einen weiteren Grund ''.join() zu verwenden?
Leonidas hat geschrieben:
lunar hat geschrieben: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

Freitag 3. Oktober 2008, 23:36

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.
Antworten