Java Kombinationen beliebiger Größe berechnen

[Xetoxyc]

ca 98 Billiarden verschiedene werte ;P x 4 Byte HF
bei 1byte pro wert sind immernoch 88 TB und das sind dann nur rein die einzelnen werte ...

ich würd schonmal von anfang an keinen int verwenden sondern nen byte
hast du 1/4 weniger speicherbedarf

falls möglich koenntest dus auch in c++ schreiben würd nochmal einiges an speed rausholen
wenn java vorgabe ist multithreading is da warscheinlich am besten

 

[IceMatrix]

Dass hier immer noch weiter über "Speed" diskutiert wird ist doch grotesk..

10^50 Möglichkeiten.. bei 1 Milliarde (10^9) Kombinationen pro Sekunde (und das is schon _sehr_ optimistisch) gibt das immernoch 10^41 Sekunden -> Das ist länger als das ganze Universum existiert!

Macht euch doch nicht zum Affen hier!

 

[Xetoxyc]

naja speed kannste schon hernehmen man nimmt ein z.b. ein botnetz zum berechnen
dann geht das schon
oder einfach ein paar cpus von amazon mieten

aba für nen normalen pc keine chance
allein schon der speicherplatz ist gigantisch

 

[yoT!mO]

@IceMatrix,
10^50 != 50^10 ;-)

Gruß Timo

 

[Helios co.]

Im Prinzip brauche nicht alle Kombinationen. Konkret brauche ich nur "einmalige" Kombinationen. Also beispielsweise 0 1 2 3 4 aber dann nicht 2 0 1 3 4 und erst recht nicht solche in denen Werte doppelt vorkommen, also 2 2 2 2 2 oder 2 2 1 3 4.


Mir ist allerdings nicht ganz klar wie ich diese von vornherein "aussortieren" soll und ob das dann wirklich so viel rechenfreundlicher ist?

Für jede so berechnete Kombination muss ich noch einen Wert berechnen, nennen wir ihn SIM. Die 20 Kombinationen mit dem kleinsten Wert SIM suche ich. D.h. ich muss nicht unbedingt alle Kombinationen speichern!

Habe die Berechnung jetzt zunächst mit 5 Threads realisiert, und es dauert, wie ihr ja schon so richtig ankemerkt habt Ewigkeiten. Nach einer Stunde kam ich auf: 0 0 0 0 0 6 49 49 49 49.

Ich denke ich gebe mich hier der höheren Macht geschlagen und versuche es mit Kombinationen der Größe 5. Selbst das dürfte einpaar Stunden dauern,was für mich aber noch vertretbar ist.

Hat jemand eine Idee,wie ich die "unnötigen" Kombinationen gar nicht erst berechnen muss?


Und einen Dank an alle für eure Beteiligung und Hilfe!

 

[chloe]

http://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n

Bei (50 über 10) sind das aber immer noch 10.272.278.170 Möglichkeiten ...

Ergänzung (5. August 2011)

Nabend!

Ich hab da mal etwas gebastelt:
http://pastie.org/2322563

CombinationFinder.combs(c, k) liefert einen Iterator über alle (c.length über k) möglichen Kombinationen der Länge k der Objekte in c. Funktioniert wunderbar.

In main() habe ich mir einen Timer gebastelt, der mir jede Sekunde die Anzahl der berechneten Kombinationen ausgibt. Ich glaube, dass die Synchronisation korrekt ist, aber das wisst ihr sicher besser als ich. Lasse ich das Ganze auf nur einem Thread laufen, kriege ich ohne Schwankungen ~6 Millionen Kombinationen pro Sekunde angezeigt. Damit ließe sich das (50 über 10)-Problem ja schon recht schnell berechnen.

Wenn ich das ganze nun auf zwei, drei oder vier Threads laufen lasse, bekomme ich entsprechend 9.5 mio, 12.8 mio bzw 12.4 mio Berechnungen pro Sekunde.
Woran liegt das? Kenne mich da überhaupt nicht aus. Naiv wie ich bin nahm ich eigentlich an, dass das Ganze linear steigen sollte.

 

[Helios co.]

Ne linear kann das eigentlich nicht ansteigen, weil du durch das Multithreading ja auch stets Overhead hast.

So weit ich weiss, verteilt das OS die Berechnungen auf freie Kerne und fügt die Ergebnisse wieder zusammen. Je mehr zu verteilen und wieder zusammenzufügen gibt um so mehr Overhead

Müsste zumindest nach meiner Denke so sein.

 

[DonnyDepp]

Im Prinzip brauche nicht alle Kombinationen. Konkret brauche ich nur "einmalige" Kombinationen. Also beispielsweise 0 1 2 3 4 aber dann nicht 2 0 1 3 4 und erst recht nicht solche in denen Werte doppelt vorkommen, also 2 2 2 2 2 oder 2 2 1 3 4.

Mir ist allerdings nicht ganz klar wie ich diese von vornherein "aussortieren" soll und ob das dann wirklich so viel rechenfreundlicher ist?

das ist ein ganz anderes szenario.
hast erfahrung mit kombinatorik, stochastik, statistik etc.?
dann könntest du dir ausrechnen, um wieviel weniger kombinationen es sich tatsächlich zwischen den beiden szenarien handelt.

ich war da immer ziemlich mies drin, deswegen zitier ich einfach mal wikipedia:
in deinem ersten code hattest du (in etwa, die komplette kombination gibts auf wiki nicht mit bildern) den fall:
Kombination mit Zurücklegen (Repetition)
"Sollen aus einer Menge von n Elementen k Elemente ausgewählt werden, wobei ihre Reihenfolge weiterhin ohne Belang sein soll, sie sich aber nun auch wiederholen dürfen, wie das z.B. beim Ziehen mit Zurücklegen möglich ist, ergibt sich für die Zahl der Möglichkeiten folgende Formel:"

deine beschreibung im ersten und im jetzigen post beschreiben aber einen anderen fall.
Kombination ohne Zurücklegen (ohne permutation)
bei k von n auszuwählenden Elementen

den unterschied siehst ja auf einen blick.


bzw. hier ist noch ne grafik

P*(10;k) ist was dein code macht, und K(10;k) ist was du eigentlich brauchst.

http://de.wikipedia.org/wiki/Abzählende_Kombinatorik

 

[Banthor]

Wenn ich das ganze nun auf zwei, drei oder vier Threads laufen lasse, bekomme ich entsprechend 9.5 mio, 12.8 mio bzw 12.4 mio Berechnungen pro Sekunde.
Woran liegt das? Kenne mich da überhaupt nicht aus. Naiv wie ich bin nahm ich eigentlich an, dass das Ganze linear steigen sollte.

Das Problem liegt in der Thread Synchronisierung. Deine Runnables machen folgendes:

for(Collection<Integer> it : CombinationFinder.combs(Main.range(50), 10)){ 
      synchronized(lockObj){
        count++; 
      }
    }

In deinem Timer machst du folgendes:

for(myRunnable mr : r){
          synchronized(mr.lockObj){
            sum += mr.count;
            mr.count = 0;
          }
        }

Wie du siehst tritt dein Runnable ununterbrochen in den synchronized block ein und aus. Gleichzeitig tritt regelmäßig Dein Timer auch in den block ein und aus und zwar auf dem selben sync Objekt. Das messen selbst also erzeugt Synchronisationbedarf in der VM, der sehr teuer sein kann.

 

[Helios co.]

Hmm, danke für den Code und den Hinweis auf die Anzahl der Kombinationen.

Ich habe den Code jetzt so weit angepasst, dass ich meine SIM Berechnungen für jede Kombination durchführen kann. Leider sinkt dabei die Anzahl der pro Sekunde generierten Kombinationen von teilweise 11 Millionen auf 30000 ab. Das würde dann wirklich Jahre dauern.

Hmm, ja keine Ahnung was ich da noch machen soll.

 

[kuddlmuddl]

Hmm, ja keine Ahnung was ich da noch machen soll.

du könntest mal sagen was der Sinn des ganzen sein soll, dann könnte man dir auch helfen
Die Dinger als String zu schreiben wirds ja für sich kaum sein.. und das das zu lange dauert war doch von vorn herein klar?

 

[Helios co.]

Nicht wirklich. Die Berechnung der Kombinationen für sich allein geht schnell. Für 5 aus 50 in weniger als 2 Minuten. Für 10 aus 50 kam der Code bei 16 Threads auf ca 11 Millionen Kombinationen in der Sekunde.

Ich brauche die Kombinationen im Grunde für 2 Verfahren die die Ähnlichkeit der enthaltenen Elemente (in der Kombination) zu einander berechnen. Bei dem ersten Verfahren werden alle möglichen (aber einmaligen AB dann nicht BA und auch keine AA etc.) Paare aus den Elementen der Kombination gebildet. Die Elemente selbst sind Indices in einer Matrix (2D Array), die die paarweisen Ähnlichkeiten enthält.

Basierend auf diesen paarweisen Ähnlichkeiten berechne ich die Gesamtähnlichkeit der Kombination.

Da ich eine Reihe unterschiedlicher Verfahren anwenden wollte, hat es sich für mich angeboten die Kombinationen als Strings zu speichern und anschließend wieder zu zerlegen. Könnte man mit Sicherheit auch eleganter machen, aber letztenendes wäre der Preformanzschub minimal.

 

[kuddlmuddl]

aber letztenendes wäre der Preformanzschub minimal.

Im Gegenteil!
Zahlen als String ablegen und dann bei der Verwendung jeder Kombination Ziffer für Ziffer jedesmal wieder in eine Zahl umwandeln? Das wird unglaublich viel Zeit kosten!
Versuch doch mal die Zahlen als solche abzuspeichern - das wird das ganze erheblich beschleunigen

 

[entropie88]

Habs mir auch mal angeschaut ich würde es absolut anders angehen. In der Tabelle Kombination ohne Zurücklegen von DonnyDepp siehst du wie du sehr schnell an die Permutationen kommst.

Mein Tipp mach dir eine boolean Matrix mit der Breite deines Wertebereichs zb k=50. Die Tiefe ist ja die Anzahl der verschiedenen Möglichkeiten und die wissen wir ja.
Eine Spalte repräsentiert eine Zahl. Eine Zeile repräsentiert eine Permutation.

Zum Starten setzt du in der ersten Spalte die ersten k Elemente true. Nun könntest du die erste Permutation auslesen alle Spalten die true sind in dieser enthalten.

Dann beginnst du nach dem Muster wie sich die roten Kästchen verschieben zu vertauschen.

Im Endefeckt hast du dann deine Ergebnisse super klein vorliegen. Und es sollte gleichzeitig auch sehr performant sein. Denn vor allem Vergleiche kosten Laufzeit, ein Integer kostet 32 mal so viel wie eine boolean Variable. Threaden kannst du es dann auch noch von oben und unten Laufen eben.

Ich hoffe du hast es verstanden wie ich es machen würde.



PS: noch ein paar Java Performance Tipps:
Wenn möglich im ersten deklaration Teil der Matrix die kleinere Zahl den so viele Objekte werden erzeugt.
Loops/Treads mit einer Exception terminieren.
Und benutzte niemals Rercursionen in Java, der Stack ist zu langsam bist ja nur in der VM.

 

[Darlis]

Loops/Treads mit einer Exception terminieren.

Hier fehlt ein "nicht". Exceptions sind doch viel teurer als ein break/return.

 

[Helios co.]

Ich denke ich habe es verstanden, aber müsste das:

Zum Starten setzt du in der ersten Spalte die ersten k Elemente true

nicht in der ersten Zeile passieren. Sprich die ersten k Elemente der ersten Zeile auf true setzen?

Damit hätte ich beim Start die erste Permutation, wie du ja gesagt hast. Für die zweite Permutation müsste ich den letzten true wert auf false setzen und den true um eine Stelle nach rechts verschieben. Und das so lange bis der rechte Rand erreicht wurde. Korrekt?

Versuch doch mal die Zahlen als solche abzuspeichern - das wird das ganze erheblich beschleunigen

Stimmt, habe es gerade getestet. Dadurch ist die Berechnung ca. um 30-50% schneller geworden. Danke für den Tipp.

 

[entropie88]

Hier fehlt ein "nicht". Exceptions sind doch viel teurer als ein break/return.

eben nicht da man durch Exceptions Kontrollmechanismen umgeht. Ist halt Java was spezielles für sich, und obs gut ist das es so ist ist eine andere Frage. Zum Thema am einfachsten mehr speed gibt's noch zu sagen die Linux implementation ist nach meinen Erfahrungen um einiges Performanter.

nicht in der ersten Zeile passieren. Sprich die ersten k Elemente der ersten Zeile auf true setzen?

Ja richtig. Hab ich verdreht. Die letzte Permutation sind alle Elemente von hinten beginnend in der untersten Zeile true setzten.

Damit hätte ich beim Start die erste Permutation, wie du ja gesagt hast. Für die zweite Permutation müsste ich den letzten true wert auf false setzen und den true um eine Stelle nach rechts verschieben. Und das so lange bis der rechte Rand erreicht wurde. Korrekt?

Richtig. Sobald du den rand erreichst setzt du die letzten beiden true auf false usw. Des müsste sich jedesmal wenn du den Rand erreichst um 1 steigern (bin mir nicht ganz sicher bei der Steigerung).

Und wie gesagt bei meiner Methode hälst du alles in dieser Matrix und ließt von dort dynamisch auß.

 

[Helios co.]

Alles klar. Ja die Idee ist wirklich gut! Thx dafür!


Nachtrag:

Hmm, die Idee mit der Bool Matrix geht leider doch nicht, schlicht aus dem einfachen Grund: Bei Fakultät von 50 reicht int nicht mehr aus und long geht eigentlich auch nicht mehr (springt ins Negative).

D.h. ich kann die Anzahl der Kombinationen nicht berechnen. Und selbst wenn ich es könnte, wäre der Wert für die Anzahl der Kombinationen immer noch größer als Int fassen kann. Int ist aber der Index für eine Bool Matrix.

 

[Sebuss]

Wie wäre es mit Listen oder Bäumen als Speicherstruktur?

Mit der Liste kannst du schnell speichern, aber ein gezielter Zugriff gestaltet sich ohne zusätzliche Verwaltungsstrukturen schwerer. Während beim Baum das Speichern aufwändiger ist, aber bei guter Ordnung das Lesen schneller.