Das deutsche Python-Forum

hallo!

Ich habe eine Liste mit mehreren Hunderttausend Elementen, die Messwerte darstellen.
Die Liste sieht etwa so aus:
a=[0,3,2,0,3,5,2...]
Das bedeutet folgendes:
Wert "0" ist 0-Mal in der Messung vorgekommen,
Wert "1" ist 3-Ma lin der Messung vorgekommen,
Wert "2" ist 2-Mal in der Messung vorgekommen,
Wert "3" ist 0-Mal in der Messung vorgekommen,
Wert "4" ist 3-Mal in der Messung vorgekommen,
usw.

Mit dieser Darstellung lässt sich gut rechnen, doch müssen zum Schluss nocheinmal die echten Werte ausgegeben werden.
Aus a=[0,3,2,0,3] muss also b=[1,1,1,2,2,4,4,4] werden.
Dies habe ich bis jetzt so gelöst:

Code: Alles auswählen

for i,j in enumerate(a): #geht alle Elemente von a durch
   for k in range(j):      #fügt in die Ausgabe-Liste die jeweilige Anzahl an tatsächlichen Werten ein
      b.append(i)

Dieser Teil verbraucht recht lange, bei Listenlängen über 1 Million schon mal ein paar Sekunden.
Meine Frage ist, ob dies nicht schneller geht.
Das Programm muss, wenn in Liste "a" an 197ter Stelle eine "5" steht, in Liste "b" 5-Mal "197" aufnehmen.

Liste "b" muss aufsteigend sortiert bleiben, vielleicht bietet sich ja aber trotzdem ein anderer Datentyp als "list" an.
Etwa die Hälfte der Zeit geht für den append-Befehl drauf, vielleicht kann das schneller gestaltet werden.

Gruß
Paul

Hallo,

Schleifen sind leider immer ziemlich langsam. Der Trick ist daher möglichst auf Schleifen zu verzichten. In deinem Fall, kannst du die innere Schleife durch ``b.extend(j*)`` ersetzen.

Grüße
Gerrit

Hallo,

ich würde das Problem - falls im konkreten Anwendungsfall möglich - ehermit einem Generator lösen. Solange du über deine Liste B also nur iterierst und nicht bestimmte Indizes abfragst, ist das vermutlich die günstigste Lösung.

Das Problem mit sehr großen Listen in Python ist letztlich, dass Python die Listengröße immer wieder dynamisch anpassen muss - und das ist recht teuer.

Besten Gruß,

brb

Ich kapiere ja nicht wirklich, wie man auf "b" kommt... sind das in der Realtität tatsächlich Integer-Werte?

Naja, hier mal mein Vorschlag für diesen mir eher theoretisch anmutenden Fall

Code: Alles auswählen

In [14]: from itertools import starmap, chain, repeat, count, izip

In [15]: list(chain.from_iterable(starmap(repeat, izip(count(), a))))
Out[15]: [1, 1, 1, 2, 2, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6]

Hallo.

Was genau hast du denn mit der Liste vor? Vielleicht kann man das geschickter lösen.

Sebastian

Allein der Fakt, dass du für jedes Element einen extra Methodenaufruf für `append()` machst, ist schon suboptimal, was sich eben bei zunehmender Menge eben auch spürbar zeigt. Aufrufe erzeugen immer gewissen Overhead, den du wie gesagt loswerden solltest.

Barabbas hat geschrieben:Das Problem mit sehr großen Listen in Python ist letztlich, dass Python die Listengröße immer wieder dynamisch anpassen muss - und das ist recht teuer.

Ist es nicht so, dass CPython jeweils um das Zweifache der aktuellen Größe verdoppelt, das Einfügen von n Elementen also in amortisiert O(n) abläuft?

Dauerbaustelle hat geschrieben:
Barabbas hat geschrieben:Das Problem mit sehr großen Listen in Python ist letztlich, dass Python die Listengröße immer wieder dynamisch anpassen muss - und das ist recht teuer.
Ist es nicht so, dass CPython jeweils um das Zweifache der aktuellen Größe verdoppelt, das Einfügen von n Elementen also in amortisiert O(n) abläuft?

Aber trotzdem kann Python z.B. bei einem Generator nicht wissen, wieviel Speicher es insgesamt anfordern muss. Insofern ist das durchaus ein ständiges Neuanfordern, solange bis eben der Iterator durch ist. Würde mich zumindest wundern, wenn dies auf andere Weise umgesetzt werden könnte. Oder werden in den Objekten nochmal Meta-Informationen zur Größe gespeichert? Selbst das dürfte dann aber nur funktionieren, wenn das Objekt / der Container bereits mitsamt seinem Inhalt besteht, was ja hier eher nicht zutrifft.

Hallo,

ich dachte jetzt ganz naiv an:

Code: Alles auswählen

def test(a):
   for i,j in enumerate(a): 
      for k in xrange(j):      
         yield i

Da sollte das Speicherproblem mMn nicht mehr auftreten - oder was meintest du jetzt?

@snafu: Trotzdem ist die Frage berechtigt ob man das "ständig neuanfordern" nennen kann. Es sind bei `n` Elementen ja nicht O(n) Anforderungen sondern nur O(log n). Wenn das mit dem verdoppelten hinkommt, wird zum Beispiel bei einer Million `append()`\s nur ca. 20 mal neuer Speicher angefordert. Und da sind im Verhältnis die Million Methodenaufrufe sicher teurer. Zumindest solange der Arbeitsspeicher nicht knapp wird und deswegen auf den Hintergrundspeicher ausgelagert wird.

Schleifen sind leider immer ziemlich langsam. Der Trick ist daher möglichst auf Schleifen zu verzichten. In deinem Fall, kannst du die innere Schleife durch ``b.extend(j*)`` ersetzen.

Das funktioniert super!
Genau nach sowas habe ich gesucht; ist ja wirklich toll, dass "j*" veranlasst, dass er J-Mal das "i" extendet.

ich würde das Problem - falls im konkreten Anwendungsfall möglich - ehermit einem Generator lösen. Solange du über deine Liste B also nur iterierst und nicht bestimmte Indizes abfragst, ist das vermutlich die günstigste Lösung.

Von Generatoren hatte ich noch nichts gehört.
Ich habe mir mal das hier
http://openbook.galileocomputing.de/pyt ... 13_004.htm
durchgelesen.
Doch bin ich mir nicht sicher, wie ich mein Problem als Generator schreiben kann.
Das ist mein Versuch:

Code: Alles auswählen

for i in xrange(len(a)):
    b.extend(a[i]*[i])

Ich kapiere ja nicht wirklich, wie man auf "b" kommt... sind das in der Realtität tatsächlich Integer-Werte?

Ja, das sind Integer-Werte.
"a" repräsentiert die Häufigkeit der Messwerte. Tritt der Messwert "87493" auf, wird das 87493te Element in "a" um eins erhöht.
Nun muss aber "a" wieder in eine Liste mit den tatsächlichen Messwerten umgewandelt werden; hat "a" an der 87493te Stelle den Wert "3", so wird in "b" nun 3-Mal "87493" aufgenommen.

Code: Alles auswählen

b=list(chain.from_iterable(starmap(repeat, izip(count(), a))))

Wow, das ist die schnellste Variante!
Ich habe nur keine Idee, was dieser Ausdruck genau tut.
Vielleicht kann mir jemand das strukturiert auseinander nehmen?

Code: Alles auswählen

def test(a):
   for i,j in enumerate(a):
      for k in xrange(j):      
         yield i

Wie würde man da jetzt den append-Befehl einbauen und "b" ausgeben lassen?
Mit "return" geht es nicht.

Peak_me hat geschrieben:
Code: Alles auswählen
def test(a):
   for i,j in enumerate(a):
      for k in xrange(j):      
         yield i
Wie würde man da jetzt den append-Befehl einbauen und "b" ausgeben lassen?
Mit "return" geht es nicht.

Gar kein `append()`, sondern einfach ein `list()` um die Funktion machen.

Peak_me hat geschrieben:
Code: Alles auswählen
b=list(chain.from_iterable(starmap(repeat, izip(count(), a))))
Wow, das ist die schnellste Variante!

Bei mir ist die `extend`-Variante schneller:

Code: Alles auswählen

def t4():
    r = []
    extend = r.extend
    for i, n in enumerate(x):
        extend([i]*n)
    return r

benötigt bei mir für eine Liste mit 20.000 Zufallszahlen zwischen 1 und 100 etwa 0.07 Sekunden, wohingegen

Code: Alles auswählen

from itertools import chain, repeat, starmap, izip, count
def t7():
    return list(chain.from_iterable(starmap(repeat, izip(count(), x))))

etwa 0,1 Sekunden braucht.

@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?

Als erstes: Hände weg vom Galileo Open Book!

Gründe dafür wurden hier im Forum zur Genüge diskutiert.

Peak_me hat geschrieben:
Code: Alles auswählen
b=list(chain.from_iterable(starmap(repeat, izip(count(), a))))
Wow, das ist die schnellste Variante!
Ich habe nur keine Idee, was dieser Ausdruck genau tut.
Vielleicht kann mir jemand das strukturiert auseinander nehmen?

Ist eigentlich gar nicht so schwer

Also fangen wir mit dem hinteren Teil an und arbeiten uns nach vorne durch.

Code: Alles auswählen

In [46]: zip(count(), a)
Out[46]: [(0, 0), (1, 3), (2, 2), (3, 0), (4, 3), (5, 5), (6, 2)]

count() ist eine Iterator-Funktion, die einfach bis von 0 bis zum Zahlenüberlauf von Integerwerten zählt. (Was passiert danach eigentlich?) In "a" stehen Deine Häufigkeiten. Mittels zip() werden immer ein Element des ersten Iterables mit dem des zweiten in ein Tupel zusammengefügt. Damit haben wir den Messwert und seine Häufigkeit zusammen generiert. Wie mir jetzt auffällt hätte man sich das auch schenken können und einfach

Code: Alles auswählen

enumerate(a)

schreiben können

repeat() ist eine Funktion, die einen Wert beliebig oft wiederholt. Wir wollen nur den Messwert entsprechend seiner Häufigkeit wiederholen.

Code: Alles auswählen

# erstes Pärchen
repeat(0, 0) -> nix
# nächstes Pärchen
repeat(1, 3) -> 1, 1, 1
# noch eines
repeat(2, 2) -> 2, 2
# schnarch...

Diese Funktion manuell aufzurufen ist Mist, also brauchen wir eine Schleife. Statt einer for-Schleife können wir aber auch eine Variante von map() nehmen, nämlich starmap(func, iterable). starmap wendet eine Funktion (1. Parameter) für alle Paare eines Iterables (2. Parameter) an:

Code: Alles auswählen

In [51]: list(starmap(repeat, enumerate(a)))
Out[51]:
[repeat(0, 0),
 repeat(1, 3),
 repeat(2, 2),
 repeat(3, 0),
 repeat(4, 3),
 repeat(5, 5),
 repeat(6, 2)]

Da repeat(1, 3) eben nicht "1, 1, 1" liefert (wie oben der Einfachheit halber noch gezeigt), sondern ein Iterator-Objekt, müssen wir diese gesammelten Iteratoren noch der Reihe nach "abarbeiten".

Code: Alles auswählen

In [63]: r = repeat(1, 3)

In [64]: r.next()
Out[64]: 1

In [65]: r.next()
Out[65]: 1

In [66]: r.next()
Out[66]: 1

In [67]: r.next()
---------------------------------------------------------------------------
StopIteration                             Traceback (most recent call last)

Aha! Nach drei mal "1" ist das Ende des Iterators erreicht.

Wir müssen nun also noch die nach und nach eintröpflenden Iteratoren nehmen und einzeln so lange "ausführen", bis deren Ende erreicht ist. Auch das könnte man mittels einer for-Schleife lösen:

Code: Alles auswählen

In [74]: for item in starmap(repeat, enumerate(a)):
   ....:     for element in item:
   ....:         print element,
   ....:
   ....:
1 1 1 2 2 4 4 4 5 5 5 5 5 6 6

Das ist auch noch unschön. Aber dafür gibt es in den Itertools chain in einer speziellen Form, nämlich chain.from_iterable(). Dieses nimmt alle Iteratoren, die in einem Iterator enthalten sind (nämlich dem einen, der durch starmap geliefert wird!) und "führt sie aus".

Ich hoffe das war einigermaßen verständlich. Sich mit den itertools und functools auseinanderzusetzen lohnt sich wirklich!

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

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.

Peak_me hat geschrieben: 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?

@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())

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

Das deutsche Python-Forum

schnelle Umwandlung

schnelle Umwandlung

Re: schnelle Umwandlung

Re: schnelle Umwandlung

Re: schnelle Umwandlung

Re: schnelle Umwandlung

Re: schnelle Umwandlung

Re: schnelle Umwandlung

Re: schnelle Umwandlung

Re: schnelle Umwandlung

Re: schnelle Umwandlung

Re: schnelle Umwandlung

Re: schnelle Umwandlung

Re: schnelle Umwandlung

Re: schnelle Umwandlung

Re: schnelle Umwandlung

Re: schnelle Umwandlung

Re: schnelle Umwandlung

Re: schnelle Umwandlung

Re: schnelle Umwandlung

Re: schnelle Umwandlung