mehrere Listen effizient optimieren

[winnitouch]

Hallo zusammen,

folgendes Problem: Ich habe mehrere Listen, sagen wir mal, 10 Stück. Jede Liste enthält ca. 2000 Elemente. Ein Element entspricht dem Kontostand an einem Tag. Der Kontostand kann über die 2000 Elemente stark schwanken, also muss nicht zwingend nur steigen, sondern kann natürlich auch sinken. Nun möchte ich diese 10 Listen in der Form optimieren, dass sie alle miteinander addiert werden sollen, jedoch mit unterschiedlicher Gewichtung. Sprich, jede Liste kann den Faktor 1-5 erhalten. Ziel ist es, aus allen 10 Listen jeweils die Gewichtung zu erhalten, welche am Ende den grössten konsolidierten Gesamtkontostand generiert - was dem letzten Element einer konsolidierten Gesamtliste entspricht.

Das Ergebnis könnte also zum Beispiel so aussehen:
3xListe1 + 1xListe2 + 1xListe3 + 4xListe5 + 5xListe6....usw.

Wie kann man das ohne zig Schleifen elegant lösen? Vor allem, weil die Anzahl Liste (hier im Beispiel = 10) dynamisch sein kann. Eventuell sind es nur 5, vielleicht auch mal 15-20. Die Anzahl hab ich in einer Variablen. Einzig die Gewichtung, also der Faktor (hier im Beispiel 1-5) ist pro Liste (!) fix festgelegt.

Gruss

[__deets__]

Ich würde dafür numpy nehmen. Aus deinen Listen kannst du dir ein Array entsprechender gesamtgrösse bauen. Und dann zb mit einem Array mit Spalten mit Faktoren multiplizieren.

[winnitouch]

Hmm...versteh ich ehrlich gesagt nicht. Kannst Du etwas ins Detail gehn?

[Sirius3]

Wenn dich sowieso nur das letzte Element interessiert, warum dann nicht einfach nur das letzte Element jeder Liste anschauen?
Wenn die Faktoren vorgegeben sind, was soll dann optimiert werden?
Ich versteh das Problem nicht.

[winnitouch]

ja hab mich evtl. falsch ausgedrückt....also die Range der Gewichtung pro Liste ist fix. Bei einer ist es evtl. 1-3, bei der anderen 1-5 usw.

[winnitouch]

Ok ich merk grad, ich hab selber noch einen Denkfehler. Wenn man einfach auf das letzte Element schaut, wird ja überall der maximale Faktor herauskommen, weil das zum grössten End-Kontostand führt.
Es muss aber die gesamte Liste berücksichtigt werden, weil Parameter wie zum Beispiel "maximaler Tagesverlust" eingehalten werden sollen.

[Sirius3]

Ach so, wir kennen also gar nicht alle Bedingungen, sollen aber helfen. product aus itertools könnte helfen, um alle Varianten durchzuprobieren.

[winnitouch]

Ich kenn selber noch nicht alle Bedingungen die ich prüfen möchte. Wollte es Euch nur erklären, damit ihr den Hintergrund versteht. Im Grunde brauch ich nach dynamischen Faktoren entsprechend x verschiedene End-Kontostandslisten, welche ich dann nach verschiedenen Bedingungen prüfe und die beste heraus nehme. Mein Hauptproblem ist eben das dynamische Generieren der verschiedenen End-Kontostandslisten, weil es zum einen unterschiedliche Anzahl Listen sein können die optimiert werden sollen und zum anderen die Range der Gewichtung pro Liste unterschiedlich sein kann...

[sparrow]

Wenn du nicht in der Lage bist die Anforderung (bzw. das Problem) zu definieren, kann das niemand lösen.

[winnitouch]

Vielleicht schreib ich meine Problemstellung nochmals neu:

folgendes Problem: Ich habe mehrere Listen, sagen wir mal, 10 Stück. Jede Liste enthält ca. 2000 Elemente. Ein Element entspricht dem Kontostand an einem Tag. Jede dieser 10 Liste kann ausserdem noch mit einem Faktor multipliziert werden, welcher in seiner Range für die einzelnen Liste unterschiedlich sein kann. Also bei Liste 1 ist der Faktor zum Beispiel zwischen 1 und 3, bei der zweiten Liste vielleicht zwischen 1 und 5 usw. Nun sollen aus allen möglichen Kombinationen entsprechend aggregierte Gesamtlisten entstehen, welche ich dann nacheinander auf verschiedene Bedingungen prüfen möchte um mir die beste Liste am Schluss heraus zu picken.
Bei 10 Listen und (vereinfacht angenommen) jede Liste hätte eine Faktorrange von 1-5 wären das aber schon 5hoch10 unterschiedliche Kombinationen, sprich End-Kontostandslisten.

Somit hab ich das Problem, dass ich zum einen nicht weis, wie ich diese dynamische Anzahl an End-Kontostandslisten erzeuge, weil evtl. sinds nicht 10 Liste sondern 8 oder 15 - das resultiert aus Code der zuvor abläuft, aber bereits verfügbar ist. Ich hab einfach ein Set aus sagen wir 100 Listen und nach diversen Kriterien werden jeden Monat x verschiedene dieser 100 Liste ausgewählt. Das ist dann eben die dynamische Anzahl der Listen, die ich nun aggregieren muss.
Und das zweite Problem ist dann eben die evtl. grosse Anzahl and End-Kontostandslisten die daraus resultieren könnte (so rein Performance technisch?)

[Sirius3]

Ich verstehe das mit dem Faktor nicht: wenn ich den größten Wert haben will, muß ich mit dem größtmöglichen Faktor multiplizieren.

[winnitouch]

Drum hab ich ergänzt, dass ich die Ergebnislisten gegen diverse Bedingungen prüfen werde. Wenn rein der End-Kontostand relevant wäre, dann wäre das korrekt, einfach grösster Faktor. Aber mal angenommen, eine der Prüfungen wird sein, wie stark der Kontostand an einem Tag maximal einbricht - und ich definier mir hier eine Obergrenze - dann werden unterschiedliche Gewichtungen der Einzellisten durchaus relevant. Aber wie gesagt, ich kenne selbst noch nicht alle Prüfbedingungen, sollte hier aber auch nicht relevant sein, denn erstmal muss ich zu allen End-Kontostandslisten kommen, und genau das ist mein Problem hier.

[Sirius3]

Bisher sehe ich nur 5*10 Varianten, weil jede Liste für sich irgendein unbekanntes, hoch geheimes Kriterium erfüllen muß. Und solange man nicht einschränken kann, wie diese Kriterien aussehen, muß man halt mit einer Schleife über alle Varianten drüber. Diese Lösung hast Du selbst schon in Deinem ersten Post gefunden. Mehr gibt es dazu, mit dem jetzigen Kenntnisstand nicht zu sagen.

[winnitouch]

Wieso 5x10? Eher 5hoch10....10 Listen mit jeweils Faktor 1-5, sind 5hoch10 Kombinationen. Es muss in jeder Kombination die Einzelliste mit dem Faktor mulipliziert werden und daraus eine neue End-Kontostandsliste erstellt werden. Diese wird dann auf zu definierende Kriterien geprüft und die beste aller End-Kontostandslisten genommen. Geht das effizienter als mit einer Schleife? Vor allem, wie geht das dynamisch? Ich hab ja nicht immer 10 Listen. Evtl. werden aus dem Pool von 100 Listen 8 ausgesucht oder 15 oder 20....

[sparrow]

Nein, es sind nicht 5 hoch 10 Varianten, weil der Faktor, über dessen Bedingung du dir nicht im Klaren bist, statisch für jedes Element der Liste ist.

Nochmal: Solange du das Problem (für dich selbst) nicht definieren kannst, kannst du es auch nicht lösen.

[Sirius3]

Bisher hast Du noch nicht erklären können, ob, bzw. wie die Listen zusammenhängen.
Aber egal. Die Antwort auf Deine Frage habe ich schon im zweiten Post gegeben.

[bords0]

Mit itertools.product könnte man zwar alle Kombinationen von Faktoren erzeugen, und dann mit numpy die gewichteten "Listen" (die dann numpy arrays sein sollten) linear kombinieren. Und dann jeweils die Bedingungen prüfen und von den Kombinationen, die alle Bedingungen erfüllen, die "beste" behalten.

Im speziellen Fall kann man das vielleicht aber besser machen. Wenn klar ist, dass es um so besser ist, je höher die Summe der gewichteten letzten Elemente ist, könnte man die Kobinationen in der Reihenfolge durchprobieren, wie sie möglichst hohe solche Summen ergeben. Diese Reihenfolge herauszufinden ist selbst eine interessante Fragestellung, aber vielleicht ist das in dem vorliegenden Fall ja einfach möglich.

Wenn die Bedingungen sehr selten erfüllt werden, hat es vermutlich jede Methode schwer. Es sei denn, du weißt doch irgend etwas über die Bedingungen, z.B. "die gewichtete Summe darf keine negativen Werte enthalten" oder so. Dann kann man sicher einiges optimieren. Aber trivial ist das eher nicht.

[winnitouch]

Wenn ich 10 Listen hab, und jede Liste könnte einen Faktor 1-5 erhalten, dann hab ich doch 5x5x5x5x5x5x5x5x5x5 unterschiedliche Kombinationen? Die Bedingungen, über die ich mir noch nicht im klaren bin, werden erst im nächsten Schritt relevant, wenn ich die Finalen Listen aller Kombinationen erzeugt habe...

[nezzcarth]

wenn ich die Finalen Listen aller Kombinationen erzeugt habe...

Wenn du es für notwendig hältst, dann mach das doch; mit dem genannten itertools-Modul (das übrigens eine sehr verständliche Doku hat... ) ist das in einer Zeile machbar...

Code: Alles auswählen

In [1]: from itertools import product, tee                                                                                                                    

In [2]: factors = product(*tee(range(1, 6), 10))

Wenn das zu einer Liste expandiert wird, verbraucht der ipython-Prozess bei mir danach schlanke 1,3 GB.