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