Seite 2 von 2

Verfasst: Montag 15. Januar 2007, 13:28
von birkenfeld
cracki hat geschrieben: __add__ von strings ist doch fuer 2 operanden (links und rechts) definiert. also kann schon mal eine optimierung fuer mehrfache addition nicht wahrscheinlich sein (ich werde jetzt nicht nachschauen, ob python da magic macht und sich ueber string.__add__ hinwegsetzt).
Das tut es, in gewissem Sinne. Die Addition zweier Strings wird direkt im Evalloop ausgeführt, und nicht erst __add__ gesucht und dann aufgerufen.
Allerdings wird bei a+b+c immer erst a+b gebildet und dann c dazuaddiert (bei der stackbasierten VM wäre das anders auch garnicht möglich).
dann waere idealerweise ein `a += b` schneller als ein `a = a + b`, denn dann koennte evtl einfach an a angehaengt werden, wenn der speicher noch alloziiert ist.
Nein, nicht im allgemeinen, da Strings immutable sind. Das Objekt "a" darf also nicht verändert werden.

Eine Ausnahme gibt es allerdings, wenn das Objekt nur durch diesen einen Namen ("a") referenziert wird. Dann wird kein neues Objekt angelegt, sondern das alte "recyclet".

Verfasst: Montag 15. Januar 2007, 13:42
von cracki
birkenfeld hat geschrieben:Nein, nicht im allgemeinen, da Strings immutable sind.
mist! was man in der hektik so alles links liegen laesst...
jedoch gut zu wissen, dass python recyclen kann (oder koennte).

Verfasst: Montag 15. Januar 2007, 14:25
von sape
@cracki: Dir ging es doch, genauso wie mir, auch darum das die Ergebnisse so "genau" wie möglich sind. Und es ist doch logisch, um so mehr "drumherum" existiert (und dann kommt noch dazu das dass "drumherum" sehr unterschiedlich ist), das sich das auf die Ergebnisse negativ auswirkt.

Z.B.: Sind deine beiden Funktionen was den Speicherverbruach (Größe der Datei, und den Verbrauch im RAM), viel besser als meine Variante. Dagegen sage ich ja auch nichts. :) Da sind wir uns alle einig.

Aber, dennoch ist deine Variante für die Sache die ich messen wollte "unbrauchbar" da zuviel Code drumherum ist, der in beiden Funktionen unterschiedlich ist. Das alles verfälscht das Messergebnis, da die "Streuung" von dem "drumherum" nicht linear ausfällt, weil das "drumherum" in beiden Funktionen von dir unterschiedlich ist.
Z.B., wie schon gesagt, verwendest du eine Schleife für die ``+`` Variante die in deiner ``%`` Variante nicht vorkommt. Dann kommt hinzu das, wie schon von Jack gesagt, eine ``x+=y + z`` in einer Iterierenden Methode nicht das gleiche ist wie eine ``x = y + z``. Und wenn man es ganz genau nimmt, dann mist du eigentlich was ganz anderes, als ich Messen wollte.

Der beste Kompromiss (Wenn es den nun stört das die Datei bei 10.000 Objekten so groß ist) das man den Generator der ``output.py`` so verändert, dass nur noch sowas erzeugt wird:

Code: Alles auswählen

str_ = "blubb"
def f1():
    return str_ + str_ + ... + N

def f2():
    return "%s%s%s ... N %(str_, str_, ... N
Den hier wird dann tatsächlich das gemacht was ich auch messen wollte. Kein drumherum sonder Explizit das was ich wissen will.

Z.B: Sieht ``output.py`` bei ``MAX_OBJ=5`` so aus:

Code: Alles auswählen

str_ = '0' * 80 #Dan eben 80 statt 3000 Zeichen.
def f1():
    return str_ + str_ +  str_ +  str_ +  str_

def f2():
    return "%s%s%s%s%s" % (str_, str_, str_, str_, str_)
Das ist die sicherste Variante, weil es Explizit das macht was ich Messen wollte. Und mehr erwarte ich auch garnicht.

BTW: Ich finde wenn man was Messen will, sollte man dafür sorgen das so wenig "streuende" Elemente wie möglich daran beteiligt sind, damit das Ergebnis so "genau" wie möglich wird.

Und mal ehrlich: Ich weiß nicht warum du da was am Testverfahren, in Bezug auf Festplattenspeicher und RAM, verbessern willst. Ist doch egal. Der Benchmark macht das was er sollte. Ich habe jedenfalls meine Ergebnisse und kann nun ruhiger schlafen da mir diese Frage nicht mehr durch den Kopf geistert ;) :D Nebenbei habe ich auch noch was mitgekriegt, wie Python mit Redundanz umgeht wenn er Bytecode erzeugt.

...

Als nächstes teste ich dann mal die ``+=`` Variante gegen die ``"".join()``-Variante in schleifen. (Ergebnisse kenne wir zwar alle aber denoch will ich das mal selber sehen). Auf die Diskussion bin ich mal gespannt :D --> Soviel kann ich schon verraten. Es wird sich am eigentlichen Verfahren nicht viel ändern. Es wird wider ein Generator benutzt der zwei Funktionen erzeugt die Genau das machen was ich testen will :D Ich werde aber keine riesige Liste mehr generieren lassen, sondern nur einen String verwenden.

lg

Verfasst: Montag 15. Januar 2007, 14:29
von BlackJack
cracki hat geschrieben:wie solls also schneller gehen? a+a+a ist nichts anderes als x += a im loop.
Mit dem Unterschied das da eine Schleife verwaltet werden muss, mit einer Laufvariablen und das die Zwischenergebnisse immer an `x` gebunden werden müssen. Es geht hier nicht um Code-Äquivalenz oder Laufzeit in O-Notation, sondern um *reale* Laufzeit. Die kann man nur für einen bestimmten Quelltext ermitteln und das Ergebnis ist nicht einfach auf Quelltext übertragbar, der das gleiche Ergebnis liefert und die gleiche Laufzeitkomplexität besitzt, aber anders zum Ziel kommt. Bei Laufzeittests sind die Konstanten wichtig die bei O-Notation rausfallen. Genau darum geht es.
iteration ist auch nix anderes als lineare rekursion, mit dem unterschied dass in primitiven sprachen jede lineare rekursion den stack zum wachsen bringt, was natuerlich genau wie iteration vernachlaessigbar wenig zeit verbraucht.

die laufzeit des loops ist linear und vernachlaessigbar. wenns sein muss kann man das sogar rausrechnen mit nem leeren loop...
Bei Laufzeittests gibt es nichts was vernachlässigbar klein ist, bevor man wirklich gemessen hat das es vernachlässigbar klein ist. Wenn man das schon vorher wüsste, bräuchte man den Test nicht. Gerade mit solchen Annahmen kann man Laufzeittests total wertlos machen.

Verfasst: Donnerstag 18. Januar 2007, 17:57
von Luzandro
Nachdem ich deinen Testaufbau auch ein wenig eigenartig gefunden habe, hab ich mir jetzt etwas Zeit genommen, selbst ein paar Tests durchzuführen, insbesondre auch, weil ja schon ein einfaches

Code: Alles auswählen

timeit.Timer('"foo"+"bar"').timeit() #0.374
timeit.Timer('"%s%s" % ("foo","bar")').timeit() #0.925
zeigt, dass dein pauschales Ergebnis "formatstring ist schneller" nicht so ganz stimmen kann.

Meine Ergebnisse: concat ist schnell für wenige Strings, wird aber für mehr Strings ab dem 2stelligen Bereich immer langsamer - bei diesen ist join am schnellsten, natürlich erst recht, wenn die Daten schon in einer Liste stehen. Irgendwo dazwischen befindet sich noch die formatstring-Methode.
Bei weitem am langsamsten (ab einer gewissen Anzahl) ist, wenn man einzelne Listenelemte per Addition verknüpft, also zB foo[0] + foo[1] +...
Klar, warum sollte man sowas tun, aber darum gehts in diesem Thread ja sowieso schon lange nicht mehr und ich habe es hinzugefügt um besser mit sapes Ergebnissen vergleichbar zu bleiben, da er von einer vorhandenen Liste ausgegangen ist. Ein Unterschied ist noch, dass ich nicht lauter gleiche Strings (und damit auch mit gleicher ID) verwende, allerdings hat das keine Auswirkung.
Eigenartig ist irgendwie noch, dass ein join, bei dem beim Aufruf eine Liste generiert wird, bei steigender Anzahl an Strings schneller ist, als wenn dem join ein vorhandenes Tuple übergeben wird..
Number of Strings 2:
0.074 seconds (100.00 %): concat
0.117 seconds (158.16 %): concat list
0.156 seconds (211.14 %): join precalculated list
0.179 seconds (243.31 %): join precalculated tuple
0.191 seconds (258.64 %): formatstring
0.193 seconds (261.66 %): formatstring with precalculated tuple
0.244 seconds (330.71 %): join
0.266 seconds (361.29 %): formatstring with single list elements

Number of Strings 42:
0.754 seconds (100.00 %): join precalculated list
1.090 seconds (144.57 %): join
1.392 seconds (184.66 %): join precalculated tuple
1.669 seconds (221.41 %): formatstring with precalculated tuple
1.671 seconds (221.72 %): formatstring
2.415 seconds (320.40 %): concat
2.871 seconds (380.88 %): formatstring with single list elements
3.216 seconds (426.61 %): concat list
Was bei den verschiedenen Methoden passiert:
concat list/tuple: ['772959', '376396'] ('772959', '376396')

concat list
concat_list[0]+concat_list[1]
772959376396

join
''.join(['772959', '376396'])
772959376396

join precalculated tuple
''.join(concat_tuple)
772959376396

join precalculated list
''.join(concat_list)
772959376396

formatstring
'%s%s' % ('772959', '376396')
772959376396

concat
"772959"+"376396"
772959376396

formatstring with single list elements
'%s%s' % (concat_list[0],concat_list[1])
772959376396

formatstring with precalculated tuple
'%s%s' % concat_tuple
772959376396

Code: Alles auswählen

#!/usr/bin/env python 
# -*- coding: utf-8 -*- 
import timeit, random

SETUP = "from __main__ import concat_list, concat_tuple"
NUMCALLS = 200000

def generateRandomStrings(numStrings):
    return [ str(random.randint(42, 1234567)) for i in xrange(numStrings) ]

code = {}
first_run = True

for i in xrange(2,40,2):
    print "Number of Strings %d:" % i
    concat_list = generateRandomStrings(i)
    concat_tuple = tuple(concat_list)

    code["concat"] = '+'.join([ '"%s"' % s for s in concat_list])
    code["concat list"] = '+'.join([ 'concat_list[%d]' % j for j in xrange(i) ])
    code["formatstring"] = "'%s' %% %s" % ("%s"*i, concat_tuple)
    code["formatstring with precalculated tuple"] = "'%s' %% concat_tuple" % ("%s"*i)
    code["formatstring with single list elements"] = "'%s' %% %s" % ("%s"*i, "(%s)" % ','.join([ 'concat_list[%d]' % j for j in xrange(i) ]))
    code["join"] = "''.join(%s)" % (concat_list)
    code["join precalculated list"] = "''.join(concat_list)"
    code["join precalculated tuple"] = "''.join(concat_tuple)"

    # on first run display what is going to be evaluated for each method 
    if first_run and i <= 10:
        print "concat list/tuple: ", concat_list, concat_tuple
        print
        for name in code:
            print name
            print code[name]
            print eval(code[name])
            print
        first_run = False
    
    results = sorted([ (timeit.Timer(code[name], SETUP).timeit(NUMCALLS), name) for name in code ])
    fastest = results[0][0]
    for r in results:
        print "%4.03f seconds (%3.02f %%): %s" % (r[0], (r[0]/fastest)*100, r[1]) #ignore ZeroDivisionException...
    print