Performance Itertools.product verbessern (multiprocessing..)

mit matplotlib, NumPy, pandas, SciPy, SymPy und weiteren mathematischen Programmbibliotheken.
Antworten
rb4k
User
Beiträge: 8
Registriert: Sonntag 10. Mai 2015, 14:38

Hallo zusammen,

ich nutze Python 2.7 mit IPython/Numpy und versuche gerade eine mehrdimensionale Liste zu formen. Dies gelingt mit im einfachen Fall, aber unter bestimmten (großen) Parameterwerten/-ausmaßen läuft mein Rechner Ewigkeiten bzw. unendlich.

Ich habe folgende Parameter als kleines Beispiel:

Code: Alles auswählen

a = [0 2 1 3 4]
b = len(a)
c = [4 3 2 1 0]
Über Itertools.product will ich jetzt alle möglichen Kombinationen ermitteln:

Code: Alles auswählen

def Condition(a, b, c):
    from itertools import product
    scope = [] 
    conditions = [] 
    array = []
    for i in range(b):
        array = array + [range(a[i])]
    for subset in product(*array):
        scope = scope + [subset]
    for subset in scope:    
        for j in range(len(c)):
            conditions = conditions + [[np.asarray(subset), c[j]]]
    np.savetxt('test.txt', conditions, delimiter=',', fmt="%s")
    return conditions
Ergebnis:

Code: Alles auswählen

[[0 0 0 0 0], 4]
…
[[0 2 1 3 4], 0]

(Die zweite „subset“-Schleife habe ich aufgrund einer leichten Performance-Verbesserung hinzugefügt. Mit ist klar, dass die in die vorhergehende integriert werden kann.)

Bei diesem Beispiel funktioniert die Funktion ohne Probleme, aber soweit ich die Parameter erhöhe (und das benötige ich fürs weitere Vorgehen), ist die Funktion nicht wirklich nutzbar. Ich meine ich brauche Parameterwerte im Bereich von len(c)=200 sowie größeren und längeren Werten in dem Arrays „c“ (so ca. jeweils 100 als Integer-Wert).

Ich habe schon versucht die Itertool-Funktion für mein Beispiel zu vereinfachen, aber das bekomme ich eindeutig nicht hin. :oops: Inwieweit ich die Funktion richtig implementiert habe weiß ich nicht (bin kein Profi). Hab nur im Internet z. B. Multiprocessing gefunden, aber die Liste als Ergebnis der Funktion hat eine Länge von 1… das hilft mir gar nicht weiter…

Code: Alles auswählen

import multiprocessing as mp
pool = mp.Pool(processes=4)
results = [pool.apply(Condition, args=(a, b, c))]
print results
Hat jemand eine Idee wie ich die Funktion verbessern kann? Oder hat jemand Erfahrung im Implementieren von Multiprocessing-Paket?? Der nächste Schritt ist übrigens auch über IPython.parallel das Problem aufm Cluster laufen zu lassen. Wer da helfen kann, der kann sich gerne an der Unterhaltung beteiligen. :D
BlackJack

@rb4k: Das Kreuzprodukt skaliert naturgemäss nicht. Rechne Dir einfach mal aus wieviele Elemente da jeweils erzeugt werden. Finde einen anderen Weg der ein besseres Laufzeitverhalten hat.
Benutzeravatar
snafu
User
Beiträge: 6731
Registriert: Donnerstag 21. Februar 2008, 17:31
Wohnort: Gelsenkirchen

@rb4k: Ein paar generelle Tipps in Sachen Perfomance:

- Wenn eh schon Numpy genutzt wird, dann möglichst viel mittels Numpy-Funktionen berechnen. Explizite `for`-Schleifen in Python dadurch weitesgehend aussparen.

- Überlegen, ob bestimmte Berechnungen (teilweise) übersprungen werden können, weil deren Ergebnisse aufgrund bestimmter Bedingungen garantiert nicht benötigt werden. Das ist natürlich immer abhängig vom Anwendungsfall, den du ja bisher nicht beschrieben hast...
Sirius3
User
Beiträge: 17711
Registriert: Sonntag 21. Oktober 2012, 17:20

@rb4k: Listen kenne append, dann muß man sie nicht ständig kopieren. Dürfte in Sachen Performance beim aktuellen Code am meisten bringen. Über Listen zu iterieren bringt nicht nur einen Geschwindigkeitsvorteil, ist auch viel schöner zu lesen.
Benutzeravatar
snafu
User
Beiträge: 6731
Registriert: Donnerstag 21. Februar 2008, 17:31
Wohnort: Gelsenkirchen

Sirius3 hat geschrieben:@rb4k: Listen kenne append, dann muß man sie nicht ständig kopieren.
...und `extend()`, wenn mehrere Elemente in einem Rutsch angehangen werden sollen. Dies wird ja anscheinend auch benötigt.
rb4k
User
Beiträge: 8
Registriert: Sonntag 10. Mai 2015, 14:38

Moin,

vielen Dank für die Antworten. :)

Habe die Funktion append() hinzugefügt und im einfachen Fall rechnet der Algorithmus etwas schneller. Die Funktion extend() konnte ich nicht sinnvoll einarbeiten. Danke trotzdem dafür!!! Hab zwar von append() gewusst, aber muss gestehen, dass ich es nicht in Betracht gezogen habe. :oops:

Also leider ist die Rechnung immer noch ziemlich lahm… Kann ich denn irgendwie einen String in seine Bestandteile zerlegen? Hab da zwar recherchiert, aber irgendwie funktioniert es nicht. Kann dann die Überlegung mit der Funktion multiprocessing wieder aufnehmen.
Eine andere Frage: (Tut mir leid… bin kein Informatiker und hab echt keine Ahnung, aber…) Kann das Ergebnis irgendwie auf der Festplatte gespeichert werden, damit der Arbeitsspeicher entlastet wird? Oder ist es unsinnig, da das speichern und einlesen zu viel Zeit verbraucht? :|

Also bin echt kein Profi, daher frag ich einfach nochmal doof...
Über Listen zu iterieren bringt nicht nur einen Geschwindigkeitsvorteil, ist auch viel schöner zu lesen.
@Sirius: Was meinst du damit? Meinst du eine Schleife ist falsch formuliert?
- Wenn eh schon Numpy genutzt wird, dann möglichst viel mittels Numpy-Funktionen berechnen. Explizite `for`-Schleifen in Python dadurch weitesgehend aussparen.
@snafu: Also ich kenne mich (leider) überhaupt nicht mit Numpy aus… Wie soll ich es denn ohne Schleifen hinbekommen? Kannst du mir einen Anhaltspunkt für meine eigene Recherche geben?
- Überlegen, ob bestimmte Berechnungen (teilweise) übersprungen werden können, weil deren Ergebnisse aufgrund bestimmter Bedingungen garantiert nicht benötigt werden. Das ist natürlich immer abhängig vom Anwendungsfall, den du ja bisher nicht beschrieben hast...
@snafu: Wenige Berechnungen (Im Vergleich zu den gesamt notwendigen Rechnungen) sind wirklich nicht nötig, aber das verkompliziert ziemlich viel und endet bei meinen Überlegungen immer in einer komplizierten Rekursion. :lol:

Danke an alle!!! :)
Sirius3
User
Beiträge: 17711
Registriert: Sonntag 21. Oktober 2012, 17:20

@rb4k: wie man Elemente einer Liste verarbeitet gehört zu den absoluten Grundlagen von Python. Also statt:

Code: Alles auswählen

array = []
for i in range(b):
    array = array + [range(a[i])]
iteriert man direkt über a:

Code: Alles auswählen

array = []
for i in a:
    array.append(range(i))
und das kann man kürzer als List-Comprehension schreiben:

Code: Alles auswählen

array = [range(i) for i in a]
das selbe gilt für die anderen Schleifen auch:

Code: Alles auswählen

from itertools import product
def Condition(a, b, c):
    array = (range(i) for i in a)
    scope = (np.asarray(subset) for subset in product(*array))
    conditions = [
        [subset.copy(), j]
        for subset in scope
        for j in c]
    np.savetxt('test.txt', conditions, delimiter=',', fmt="%s")
    return conditions
rb4k
User
Beiträge: 8
Registriert: Sonntag 10. Mai 2015, 14:38

Sirius3 hat geschrieben:wie man Elemente einer Liste verarbeitet gehört zu den absoluten Grundlagen von Python.
Gut, dass ich mir die Grundlagen selbst beibringen muss. :D Sorry, aber hab das Beispiel vereinfacht und dadurch diesen unnötigen Schritt über b gemacht. ^^

Ich gucke mir deine Lösung mal an, da ich sie auf Anhieb nicht lesen kann bzw. verstehe… Aber trotzdem danke. Das hilft mir bestimmt das Problem besser zu implementieren. :)
Benutzeravatar
snafu
User
Beiträge: 6731
Registriert: Donnerstag 21. Februar 2008, 17:31
Wohnort: Gelsenkirchen

rb4k hat geschrieben:Das hilft mir bestimmt das Problem besser zu implementieren. :)
Implementiere doch besser *die Lösung* für für das Problem. :twisted:
@snafu: Also ich kenne mich (leider) überhaupt nicht mit Numpy aus… Wie soll ich es denn ohne Schleifen hinbekommen? Kannst du mir einen Anhaltspunkt für meine eigene Recherche geben?
Numpy bietet eine ganze Reihe von Funktionen, die es erlauben, Python-Schleifen einzusparen. Die Schleifen werden zwar intern trotzdem gemacht, aber eben nicht in Python, sondern in einer Programmiersprache, die Schleifen deutlich schneller ausführt als Python. Das ist die Idee dahinter. Details findest du in der Numpy-Dokumentation.
rb4k
User
Beiträge: 8
Registriert: Sonntag 10. Mai 2015, 14:38

Die Lösung habe ich doch… Dauert halt nur ne gewisse Zeit. :lol:

Danke für den Tipp und ich verstehe jetzt langsam die Vorteile von NumPy und was @snafu meint. Hab eine gute Lösung auf http://stackoverflow.com/a/1235363/4913569 gefunden und mit zwei unschönen „Schleifen“ - bekomme es vorerst nicht anders hin - konnte ich es für meine Problemstellung nutzen. Rechenzeit ist jetzt ein Bruchteil… aber immer noch nicht ausreichend zur Anwendung auf meinem privaten Rechner. :oops:

Jetzt macht mir zwar eine andere Funktion mit der Rechenzeit Sorgen, aber weiß wie ich jetzt suchen muss. Danke. :D
Benutzeravatar
snafu
User
Beiträge: 6731
Registriert: Donnerstag 21. Februar 2008, 17:31
Wohnort: Gelsenkirchen

Die Herausforderung ist halt, sein Problem "numpysch" zu formulieren. Das erfordert ein bißchen Übung und Kenntnisse über die Möglichkeiten von Numpy. Aber für aufwändige Berechnungen ist es die Mühe oft wert.
Antworten