schnelle Umwandlung

[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

[BlackJack]

Grrr, wenn man in der innersten Schleife etwas ungünstiges macht… In C ist es dann doch schneller als `psyco`. Hier nochmal die aktuellen Ergebnisse:

Code: Alles auswählen

01.  0.057073  x13.57    BlackJack 2 (C)
02.  0.066183  x11.70    Original +psyco
03.  0.077075  x10.05    Dauerbaustelle 2 +psyco
04.  0.080290  x 9.64    BlackJack 1 (Cython)
05.  0.280389  x 2.76    Dauerbaustelle 1 +psyco
06.  0.315110  x 2.46    Original (Cython)
07.  0.342334  x 2.26  * Hyperion 2 (enumerate())
08.  0.343112  x 2.26    Hyperion 2 (enumerate()) +psyco
09.  0.356104  x 2.17    Dauerbaustelle 1 (Cython)
10.  0.360772  x 2.15  * Hyperion 1 (count())
11.  0.360916  x 2.15    Hyperion 1 (count()) +psyco
12.  0.466697  x 1.66  * Dauerbaustelle 1
13.  0.774309  x 1.00  * Original
14.  0.784385  x 0.99  * Dauerbaustelle 2

Edit: Und noch einmal aktualisiert. Nun haben wir auch eine Lösung die bei mir geringfügig langsamer läuft als das Original. '*' bedeutet reines Python, also nicht in C oder mit `psyco`.

[BlackJack]

Mir viel gerade auf, dass ich die C-Lösung gar nicht veröffentlicht hatte: http://paste.pocoo.org/show/369284/

Ist im Grunde die Originalvariante als C-Erweiterung.