schnelle Umwandlung

[Peak_me]

@Dauerbaustelle:
[quote]Bei mir ist die `extend`-Variante schneller:

Code: Alles auswählen

benötigt bei mir für eine Liste mit 20.000 Zufallszahlen zwischen 1 und 100 etwa 0.07 Sekunden, wohingegen
[Code itertools]
etwa 0,1 Sekunden braucht.[/quote]

Bei mir ist eindeutig die "itertools"-Variante von Hyperion schneller. Vermutlich liegt das an deinen Zufallswerten.
"a" enthält fast nur Elemente mit den Werten 0 bis 3, es ist recht selten, dass häufiger als 3-Mal die gleichen Messwerte auftreten.

@BlackJack
[quote]@Peak_me: Was willst Du denn mit `b` machen? "Ausgeben" sagt das nicht wirklich aus. Brauchst Du `b` dafür komplett als Liste oder reicht es wenn Du über die Werte iterieren kannst?[/quote]
Es werden Auszüge dieser Liste dem Benutzer ausgegeben. Ich brauche also "b" in der Tat komplett.

---
Den neuen Beitrag von Hyperion, der währen des Schreibens aufgetaucht ist, lese ich mir gleich durch.

[EyDu]

Und warum brauchst du die vollständige Liste, wenn du nur Teile davon ausgeben möchtest? Du hast doch bereits die Anzahl der einzelnen Elemente, dann ist es auch nicht mehr schwer nur noch den entsprechenden Teil zu bestimmen.

[Hyperion]

Bei mir ist eindeutig die "itertools"-Variante von Hyperion schneller. Vermutlich liegt das an deinen Zufallswerten.

Na, ich hoffe doch mal, dass Dauerbaustelle das Experiment mit densselben Zufallszahlen bei beiden Varianten durchgeführt hat

Mich würde mal interessieren, ob sich die Subvariante meines Vorschlags mit enumerate() auf die Zeit auswirkt?

[BlackJack]

@Hyperion: Ja tut es. Beide Varianten sind auch bei mir schneller als die `extend()`-Lösung von Dauerbaustelle. Rahmenbedingung: `a` = 500k Zufallswerte von 0 bis 4, random.seed(0) um Wiederholbarkeit (zumindest lokal) zu ermöglichen. Ergebnis ca. 100k Einträge. Da wäre von Peak_me vielleicht eine Einschätzung nötig ob das Verhältnis so ungefähr realistisch ist, oder ob es zu viele 0en in `a` gibt. Hier die Zeiten (beste von jeweils 10 Wiederholungen) in Sekunden:

Original: 0.481042146683
Dauerbaustelle extend() and *: 0.247262954712
Hyperion 1 (count()): 0.194404125214
Hyperion 2 (enumerate()): 0.185117006302

Edit: Mit `import psyco; psyco.full()`:

0.043738126755 Original
0.154628038406 Dauerbaustelle (extend() and *)
0.194642066956 Hyperion 1 (count())
0.185706138611 Hyperion 2 (enumerate())

[Hyperion]

@BlackJack: Vielen Dank für die Durchführung der Experimente und der Veröffentlichung

[Dauerbaustelle]

Hier mal meine Testdaten. http://paste.pocoo.org/raw/366489/

Wäre auch mal interessant mit PyPy laufen zu lassen. Da hat man ja wieder ganz andere Optimierungsstrategien. Ich fände auch interessant, wie gut sich PyPy bei diesem itertools/functools-Gedönz schlägt. Ich vermute aber mal, dass die Originallösung am schnellsten ist. Wer mag? :-)

[BlackJack]

@Dauerbaustelle: Mit Deinem Datensatz * 4 (damit das nicht zu schnell läuft) ist Dein Ansatz geringfügig schneller als die beiden von Hyperion (aufsteigend sortiert):

0.074934005737 BlackJack (Cython)
0.078186988831 Original +psyco
0.091145992279 Dauerbaustelle (extend() and *) +psyco
0.108819961548 Dauerbaustelle (extend() and *)
0.121788978577 Hyperion 2 (enumerate())
0.122401952744 Hyperion 1 (count())
0.756856918335 Original

Der hauchdünne "Sieger" von mir sieht so aus:

Code: Alles auswählen

def f_7(histogram):
    cdef int i = 0, j, k
    result = [None] * sum(histogram)
    for j from 0 <= j < len(histogram):
        count = histogram[j]
        if count:
            value = j
            for k from 0 <= k < count:
                result[i] = value
                i += 1
    return result

Es kommt also auf die Eingangsdaten an. Vielleicht kann `Peak_me` ja mal ein Histogramm von so einem `a` zeigen!?

PyPy ist noch auf dem Stand von Python 2.5, da gab es noch kein `chain.from_iterable()`, wäre also auch nicht wirklich vergleichbar.

[Dauerbaustelle]

Achso, ich nahm an, dass die 2.6-kompatibel sind, weil ja grade aktiv an 2.7-Support gewerkelt wird. btw, vielleicht ist das explizit so gedacht, aber Cython konvertiert `xrange`/`range` implizit zu `for ... from ...`.

[Dauerbaustelle]

Ha, mit BlackJacks Pre-Allokation wird meine Variante noch schneller.

Code: Alles auswählen

def t8():
    r = [None]*sum(x)
    for i, n in izip(count(), x):
        r[i] = n
    return r

[Peak_me]

Vielleicht kann `Peak_me` ja mal ein Histogramm von so einem `a` zeigen!?

Ich habe mal eine txt-Datei mit 1.000.000 Werten hochgeladen.
http://rapidshare.com/files/456178271/a.txt
Hier ist das Histogramm davon:
0: 368061
1: 367304
2: 184469
3: 61285
4: 15194
5: 3095
6: 506
7: 75
8: 8
9: 3
Erklärung: "0" tritt 368061-Mal auf, "1" tritt 368061-Mal auf usw.
Höhere Zahlen als "9" treten nicht auf.

Hier ein Pastebin mit 10.000 Werten:
http://pastebin.com/AqhvVutm


Gruß
Paul

[Dauerbaustelle]

Hier mal für die Filehostern abgeneigten: http://jonas.lophus.org/a.data

[BlackJack]

Okay hier sind die Ergebnisse mit dem 1M Datensatz:

0.066145181656 Original +psyco
0.076053142548 BlackJack (Cython)
0.297075033188 Dauerbaustelle (extend() and *) +psyco
0.323311805725 Original (Cython)
0.347491979599 Hyperion 2 (enumerate())
0.359014987946 Dauerbaustelle (extend() and *, Cython)
0.363184928894 Hyperion 1 (count())
0.457803964615 Dauerbaustelle (extend() and *)
0.773974895477 Original

[Hyperion]

Hier mal für die Filehostern abgeneigten: http://jonas.lophus.org/a.data

Hätte das Histogramm nicht einfach gereicht?

[Peak_me]

Ich arbeite mich mal langsam durch alle Beiträge.

zu Hyperion:

Hyperion /// Betreff des Beitrags: Re: schnelle Umwandlung /// BeitragVerfasst: Mi Apr 06, 2011 12:56
Ist eigentlich gar nicht so schwer

vielen Dank für die tolle Erklärung! Ich weiß nun, was alle Teile tun und kann sie für dieses Problem benutzen, doch wenn in einiger Zeit ein neues auftritt, werde ich meine Probleme mit der Syntax haben.

Sich mit den itertools und functools auseinanderzusetzen lohnt sich wirklich!

Das sieht tatsächlich so aus; ich füge es in meinem Hinterkopf der To-Do-Liste hinzu.

Hyperion /// Betreff des Beitrags: Re: schnelle Umwandlung /// BeitragVerfasst: Mi Apr 06, 2011 08:47
list(chain.from_iterable(starmap(repeat, izip(count(), a))))

Hyperion /// Betreff des Beitrags: Re: schnelle Umwandlung /// BeitragVerfasst: Mi Apr 06, 2011 12:56
In [46]: zip(count(), a)

Wieso benutzt du einmal "izip" und einmal "zip"? Wo ist der Unterschied?

[Xynon1]

Der Unterschied ist, das du ein Iterator und keine Liste bekommst. Du wolltest dich doch mit den "itertools" auseinander setzen, fang doch am besten gleich da an.

[BlackJack]

Ich habe gerade mal das Original als C-Erweiterung umgesetzt. Das ist zwar schneller als mein Cython-Code, aber *langsamer* als das Original mit `psyco` beschleunigt:

0.067362070087 Original +psyco
0.071317195892 BlackJack (C)
0.080206155777 BlackJack (Cython)

Wenn man jetzt den Aufwand vergleicht das in C zu schreiben, mit dem simplen Import + Funktionsaufruf bei `psyco`…

[Hyperion]

So, ich habe mich auch mal von der Allokation inspierieren lassen und meine Variante ein wenig ergänzt:

Code: Alles auswählen

def hyperion_3(x):
    r = [None]*sum(x)
    r.append(chain.from_iterable(starmap(repeat, enumerate(x))))
    return r

Zusätzlich habe ich mal Dauerbaustelles t8-Script mit enumerate probiert:

Code: Alles auswählen

def t9(x):
    r = [None]*sum(x)
    for i, n in enumerate(x):
        r[i] = n
    return r    

Hier die Ergebnisse:

Hyperion1 (izip + count): 1.00264921938
Hyperion2 (enumerate): 1.08713984599
Hyperion3 (Allokation + enumerate): 0.296305256674
Hyperion4 (Allokation + izip + count): 0.298081739439
Dauerbaustelle t8 (Allokation + izip + count): 0.187671338117
Dauerbaustelle t9 (t8 mit enumerate): 0.187594233345


Erkenntnisse:
- Bei meinen Ansätzen scheint das list() viel Zeit zu kosten.
- ob mit enumerate oder izip + count scheint sich kaum zu unterscheiden
- bei meiner ersten Lösung kostet enumerate eher als dass es nützt

Hier mal der Link zu meinem Testscript.
@BlackJack: Ich glaube Du hast das umfangreichste Script. Evtl. kannst Du das ja mal um meine neue Variante + Dauerbaustelles "t8" ergänzen und online stellen?

[Dauerbaustelle]

So, ich habe mich auch mal von der Allokation inspierieren lassen und meine Variante ein wenig ergänzt:

Code: Alles auswählen

def hyperion_3(x):
    r = [None]*sum(x)
    r.append(chain.from_iterable(starmap(repeat, enumerate(x))))
    return r

Äh das soll `extend` heißen, nich? Man sollte den Tester vielleicht noch in der Hinsicht erweitern, dass er die Rückgaben der einzelnen Varianten vergleicht...

Edit: Dann wäre mir auch mal aufgefallen, dass meine letzte Variante (`t8`) gar nicht korrekt ist.

[Dauerbaustelle]

http://paste.pocoo.org/show/366850/ Hier mal das Testscript mit den genannten Verbesserungen, außerdem zwei funktionierenden Implementationen meinerseits. (Diff: http://paste.pocoo.org/compare/366850/366804/) Anscheinend läuft irgendwas in deinen Implementationen schief, Hyperion. Gut wäre auch noch die unoptimierte Standardversion als Referenz zu haben.

Edit: Und dann vielleicht die vom OP genannten Beispieldaten drauflaufen lassen.

Das schreit ja fast schon nach 'ner Webapp! :-D

[Hyperion]

Äh das soll `extend` heißen, nich? Man sollte den Tester vielleicht noch in der Hinsicht erweitern, dass er die Rückgaben der einzelnen Varianten vergleicht...

Stimmt Oh mein Gott, was hab ich da für nen Unsinn verzapft

Ich sollte zu Bett gehen