---

Geschrieben von Boldoran am 10.11.2008 um 20:47:

  Quadrupel berechnen

Hallo

Ich habe Probleme mit der Rechenzeit von folgender Aufgabe:
Ich habe eine Collection mit 750 Punkten. Nun versuche ich alle möglichen Quadrupel (x1,x2,x3,x4) zu finden für die folgendes gilt:
x1 != x2
x3 != x4
(x1,x2) != (x3,x4)

Mein Java-Algorithmus berechnet zur Zeit erst alle möglichen Paare

code: 1: 2: 3: 4: 5: 6: 7: 8: 9: for (int i = 0; i < datasetSize; i++) { for (int j = i + 1; j < datasetSize; j++) { //indize des paares (x1, x2) merken pairs.add(new int[] { i, j }); } }

Danach wende ich das gleiche Verfahren auf die so konstruierte Liste von Paaren an und berechne somit Quasi alle möglichen Paare von Paaren.
Diese Berechnung Funktioniert für kleine Datenmengen aber für die 750 Punkte dauert es zu lange. Ich habe versucht auszurechnen wieviele Paare von Paare es gibt und ich kam auf 3.9 *10^10. Stimmt diese Zahl? Gibt es für diese Berechnung einen effizienteren Weg?

Grüsse

---

Geschrieben von ed209 am 11.11.2008 um 12:44:

 

Ich bin mir nicht ganz sicher ob ich das Problem richtig verstanden hab, aber es scheint mir daß deine Lösungsmenge in ähnlich gewaltiger Größenordnung ist. Ich verstehe das so, daß du eine Menge mit 750 verschieden Elementen hast und suchst ein 4-Tupel mit (x1, x2, x3, x4) mit genannten Bedingungen.

Wäre die (stärkere) Bedingung, daß alle Punkte verschieden sind, würdest du immernoch lösungen erhalten.

Wenn deine Ausgabe schon so groß ist, kann deine Laufzeit mit konventionellen Methoden nicht geringer sein

---

Geschrieben von Boldoran am 11.11.2008 um 21:28:

 

Ja du hast mich richtig verstanden. Trotzdem bin ich einigermassen erstaunt dass das pure abarbeiten der for-Schleifen 15 -20 Minuten dauert.

Als mögliche tuningideen sind mir bisher 2 Dinge eingefallen.

- Die Berechnung der möglichen Quadrupel könnte vor dem eigentlichen ausführen des Programmes erfolgen. Dies würde dann aber den Speicherverbrauch in die höhe Treiben. Ausserdem möchte ich die grösse der Inputmenge nicht vorfixieren.

- Könnte man den Berechnungsvorgang irgendwie parallelisieren um evtl vorhandene Mehkernprozessorsysteme besser auszunutzen?

---

Geschrieben von ed209 am 12.11.2008 um 13:01:

 

Eigentlich nicht, da dein Problem nicht ist daß es lange dauert eine Lösung zu berechnen, sondern du zuviele Lösungen hast.

Was genau willst du mit den gefundenen Lösungen denn eigentlich machen?

Wenn du zm Beispiel alle 39 Milliarden Lösungen auf Kommandozeile ausgeben willst, dann ist dein Flachenhals sicherlich den Outbuffer, und da hilft dir dann
auch kein parallelisieren.

---

Geschrieben von Tobias am 12.11.2008 um 16:34:

 

Du redest hier von Punkten. Sind das tatsächlich Koordinatenpaare (x- und y-Wert)? Wenn dem so ist, dann ist ein Quadrupel (x1, x2, x3, x4) also ein Punktepaar ((x1, x2), (x3, x4))? Was ist tatsächlich in deiner Collection drin?

Deine Java-Algo berechnet nicht alle geordneten Paare sondern alle ungeordneten Paare. Zu den geordneten Paaren würde z.B. das Paar (5,1) genauso wie der Paar (1,5) gehören. Deine Schleife berechnet aber nur (x, y) mit y > x.

---

Geschrieben von Boldoran am 24.11.2008 um 16:19:

 

Zitat:

Deine Java-Algo berechnet nicht alle geordneten Paare sondern alle ungeordneten Paare. Zu den geordneten Paaren würde z.B. das Paar (5,1) genauso wie der Paar (1,5) gehören. Deine Schleife berechnet aber nur (x, y) mit y > x

Das ist korrekt. Ich brauche nur ungeordnete Paare. Bei der ganzen Sache geht es darum einen Index zur Cluster Validierung zu berechnen und zwar geht es um den Goodman Kruskal Index. In der Collection sind Merkamalsvektoren enthalten.

Bei diesem Index vergleicht man jeweils paare von solchen Merkmalsvektoren auf ihre Distanz und auf ihre Clusterzugehörigkeit um ein Mass für die Güte des Clusterings zu bekommen. Ausgegeben wird bis auf das Endresultat nichts aber natürlich erfordert die Distanzberechnung nochmal einiges an Rechenzeit.

Ich war nur etwas erstaunt dass bereits das durchlaufen aller möglichen Paare ungeordneten Paare (ohne irgend eine Aktion in der Forschleife) ~20 Minuten gedauert hat. Durch die grösse des Datensatzes scheint dies bei der Berechnung diese Indexes aber unvermeidlich zu sein.