Registrierung Kalender Mitgliederliste Teammitglieder Suche Häufig gestellte Fragen Zur Startseite

Informatiker Board » Themengebiete » Praktische Informatik » Quadrupel berechnen » Hallo Gast [Anmelden|Registrieren]
Letzter Beitrag | Erster ungelesener Beitrag Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen
Neues Thema erstellen Antwort erstellen
Zum Ende der Seite springen Quadrupel berechnen
Autor
Beitrag « Vorheriges Thema | Nächstes Thema »
Boldoran
Grünschnabel


Dabei seit: 10.11.2008
Beiträge: 3

Quadrupel berechnen Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Boldoran: 10.11.2008 20:48.

10.11.2008 20:47 Boldoran ist offline E-Mail an Boldoran senden Beiträge von Boldoran suchen Nehmen Sie Boldoran in Ihre Freundesliste auf
ed209
Routinier


Dabei seit: 07.09.2006
Beiträge: 324

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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 [latex] \begin{pmatrix} 750 \\ 4 \end{pmatrix} [/latex] lösungen erhalten.

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

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von ed209: 12.11.2008 12:57.

11.11.2008 12:44 ed209 ist offline E-Mail an ed209 senden Beiträge von ed209 suchen Nehmen Sie ed209 in Ihre Freundesliste auf
Boldoran
Grünschnabel


Dabei seit: 10.11.2008
Beiträge: 3

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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?
11.11.2008 21:28 Boldoran ist offline E-Mail an Boldoran senden Beiträge von Boldoran suchen Nehmen Sie Boldoran in Ihre Freundesliste auf
ed209
Routinier


Dabei seit: 07.09.2006
Beiträge: 324

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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.
12.11.2008 13:01 ed209 ist offline E-Mail an ed209 senden Beiträge von ed209 suchen Nehmen Sie ed209 in Ihre Freundesliste auf
Tobias
Routinier


Dabei seit: 18.09.2006
Beiträge: 324

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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.
12.11.2008 16:34 Tobias ist offline E-Mail an Tobias senden Beiträge von Tobias suchen Nehmen Sie Tobias in Ihre Freundesliste auf
Boldoran
Grünschnabel


Dabei seit: 10.11.2008
Beiträge: 3

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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.
24.11.2008 16:19 Boldoran ist offline E-Mail an Boldoran senden Beiträge von Boldoran suchen Nehmen Sie Boldoran in Ihre Freundesliste auf
Baumstruktur | Brettstruktur
Gehe zu:
Neues Thema erstellen Antwort erstellen
Informatiker Board » Themengebiete » Praktische Informatik » Quadrupel berechnen