Effiziente String-Verkettung

Gute Links und Tutorials könnt ihr hier posten.
epsilon
User
Beiträge: 71
Registriert: Freitag 20. Juni 2008, 19:48

Effiziente String-Verkettung

Beitragvon epsilon » Mittwoch 2. Juli 2008, 16:32

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

Beitragvon Leonidas » Mittwoch 2. Juli 2008, 18:15

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

Beitragvon epsilon » Mittwoch 1. Oktober 2008, 17:01

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.


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

Beitragvon BlackJack » Mittwoch 1. Oktober 2008, 18:04

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

Beitragvon lunar » Mittwoch 1. Oktober 2008, 18:48

Bild
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
User
Beiträge: 71
Registriert: Freitag 20. Juni 2008, 19:48

Beitragvon epsilon » Mittwoch 1. Oktober 2008, 19:45

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

Beitragvon lunar » Mittwoch 1. Oktober 2008, 22:05

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.

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
User
Beiträge: 71
Registriert: Freitag 20. Juni 2008, 19:48

Beitragvon epsilon » Donnerstag 2. Oktober 2008, 00:27

lunar hat geschrieben:
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.

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


Oh, stimmt, dran hatte ich gar nicht gedacht ;)

lunar hat geschrieben:
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

Beitragvon lunar » Donnerstag 2. Oktober 2008, 10:12

epsilon hat geschrieben:
lunar hat geschrieben:
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
User
Beiträge: 1454
Registriert: Freitag 22. September 2006, 23:05
Wohnort: ja

Beitragvon Y0Gi » Donnerstag 2. Oktober 2008, 10:48

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

Beitragvon BlackJack » Donnerstag 2. Oktober 2008, 13:22

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
User
Beiträge: 71
Registriert: Freitag 20. Juni 2008, 19:48

Beitragvon epsilon » Freitag 3. Oktober 2008, 19:39

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

Beitragvon Leonidas » Freitag 3. Oktober 2008, 19:47

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

Beitragvon epsilon » Freitag 3. Oktober 2008, 21:36

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

Beitragvon Leonidas » Freitag 3. Oktober 2008, 21:46

epsilon hat geschrieben: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.

epsilon hat geschrieben:Was genau hast damit denn gemeint?

Ich habe damit gemeint, dass trotz der Verbesserungen in CPython ``''.join()`` dennoch bevorzugt werden sollte.
My god, it's full of CARs! | Leonidasvoice vs Modvoice

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder