Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
7.5 ClosestPair
Hallo,
in der Aufgabe b) steht “all die Punkte, die von einem Punkt middle höchstens +/- distance in x-Richtung entfernt sind”, nun gibt es in der ClosestPair Klasse die Funktion distance,
diese berechnet aber die 2 Dimensionale Entfernung und nicht den Abstand in x-Richtung.
Ist tatsächlich nur der Abstand in x-Richtung gemeint oder soll man die distance Funktion verwenden?
Edit: Nevermind, hätte die c) lesen sollen;)
Mir ist nochnicht ganz klar wie die Rekursion im ForkJoinPool richtig funktioniert.
Ich erstelle in der compute methode meines RecurisveTask einen neuen recursiveTask, dessen compute ich dann wieder aufrufe.
mach das sinn? leider ist das nicht wirklich schneller als die sequentielle Variante…
In der sequentiellen Variante hast du ja zwei rekursive Aufrufe (einen für die linke Hälfte, einen für die rechte). In der parallelen Variante erstellst du nun ein Arbeitspaket (von RecursiveTask abgeleitet) für die linke Hälfte und eines für die rechte Hälfte. Auf einem von beiden kannst du dann [m]fork()[/m] aufrufen (führt das Arbeitspaket auf einem eigenen Thread aus), auf dem anderen [m]compute()[/m] (führt das Arbeitspaket auf dem gleichen Thread aus). Das Ergebnis des geforkten Arbeitspaket bekommst du mit [m]join()[/m]. Schau dir auch mal das Beispiel in der Java-API-Dokumentation zu RecursiveTask an, das macht genau das am Beispiel der Berechnung von Fibonacci-Zahlen.
Ich habe auch eine Frage zum Parallelisieren. Wenn ich fork(), compute() und join() ausgefuehrt habe, muss ich die zwei Ergebnisse ja wieder verarbeiten. Das Verarbeiten muss ich dann 1 zu 1 wie in der sequientiellen Variante machen oder? Ich kann also sequientialImpl verwenden, um merge() und filter() aufzurufen?
Und noch ne Frage :
Ich habe als treshold alles moegliche zwischen 4 und 40000 ausprobiert und die Laufzeit ist beim Auslastungstest immer “SequentialTime: 23.032 ParallelTime: 15.927”. Heisst das, dass ich etwas falsch mache? Auch wenn ich mir die Prozessorauslastung mit [m]htop[/m] anschaue, dann sind bei der parallelen Version kurz am Anfang alle 4 Kerne belastet, dann relativ kurz zwei Kerne zu 100% und die restlichen 7-8 Sekunden ist nur noch ein Kern bei 100% und die anderen drei bei 0-2% (gleiches Ergebnis bei unterschiedlichen tresholds). Das sollte nicht so sein oder?
Ja 
.
Nicht wirklich. Da merge/filter ebenfalls aufwendig sind, fällt der Overhead durch das zusätzliche Erstellen von
RecursiveTasks nicht sonderlich ins Gewicht. Bei kleineren Problemgrößen kann man etwas Unterschied feststellen.
Es geht auch weniger darum für den Test die passenden Schranken zu finden, sondern darüber nachzudenken, ob eine Konstante bei unterschiedlichem
Parallelisierungsgrad und unterschiedlichen Problemen so viel Sinn macht ;).
Doch, das ist Divide and Conquer und der letzte merge-Schritt ist aufwändig ;). Du darfst natürlich zusätzlich merge freiwillig parallelisieren, dann wird
das besser ;). Das ist aber nicht trivial (siehe http://drdobbs.com/high-performance-computing/229204454 ).
Ist es so gewollt, dass laut Test-Cases zum einen der Parameter start von getClosestPair inklusiv ist, sprich man bei Index start vom Daten-Array beginnt, end allerdings ist exklusiv, da bei den Test-Cases getClosestPair(points, 0, points.length) aufgerufen wird.
Ist das so gewünscht oder wie kann ich damit umgehen? 
Entspricht das nicht auch der Definition im Interface?
Ist der Hinweis bei ParallelPerformanceTest “Takes several minutes!!!” nicht etwas übertrieben? Bei mir dauert der ganze Test 1,7 Sekunden ^^
Oder hab ich da was falsch gemacht?
Der beste Threshold zum Umstieg auf die sequentielle Variante ist doch wohl auf jedem System unterschiedlich und dürfte sich grob an der Anzahl der Kerne orientieren, oder?
Nein, aber wenn du merge ungeschickt implementierst, kanns mehrere Minuten dauern ;).
Ja, wenn kein Parallelisierungsgrad vorgegeben ist, sind die Kerne eine gute Richtschnur.
edit:
Ungeschickt ist ein remove() bei ner ArrayList und ein get() bei ner LinkedList ;).
Ah ja, das macht natürlich Sinn. Man sollte die Arraylist eben auch als solche nutzen ^^
merke: Arraylists werden ungern vergewaltigt.
Ich glaube mitlerweile aber, dass das so nicht stimmt… Denn genau diese Aufgabe sollte ja eigentlich der ForkJoinPool übernehmen, dafür übergibt man ihm ja den parallelitätsgrad.
Kann es sein, dass man ihn quasi „unterstützen“ soll, indem man mit dem forken etc aufhört, sobalt (end-start)<threshold?
Dann fällt der Overhead durch den Threadpool weg, auf der anderen Seite wird dieser dann auch relativ nutzlos… und ich ratlos.
Bei mir hakts noch am sequentiellen Algorithmus.
Speziell unterscheiden sich die Ergebnisse beim SimpleSmallValueTest minimal - stark (0.002 - 1.0 ca.) von meinen.
Daher nochmal, um sicherzugehen dass ich das Prinzip des Algorithmus richtig verstanden habe:
Ich teile mein Daten-Array so lange rekursiv auf, bis ich eine gewisse Mindestmenge von Punkten habe. (zB 4)
Diese lasse ich dann Bruteforcen. Damit bekomme ich 2 Punkte sowie eine Liste von y-sortierten Punkten.
Danach merge ich die in meinem baum wieder die ersten 2 results, gucke also welches von beiden ein geringeres Delta produziert, und setze je nachdem sowohl mein delta als auch mein Ergebnis (vorläufig).
Danach filtere ich meine y-Liste auf Abstände zum Punkt start.x + (end-1).x/2 (bisschen pseudocode…).
Als letztes nehme ich meine gefilterte Liste, vergleiche jeden Punkt mit seinem oberen Nachbarn in der Liste (falls vorhanden, beginnend beim ersten), und prüfe ob der y-Abstand < meinem vorher gesetzten Delta ist.
Falls ja, berechne ich mir mein neues Delta erneut durch pointA.distance(pointB), setze pointA und pointB in meinem ret als neue rückgabewerte, und prüfe weiter ob noch Punkte mit geringerem y-Abstand als Delta gefunden werden.
Und so weiter, bis ich wieder ganz oben beim initialen Aufruf angekommen bin und ein endgültiges Ergebnis erreiche.
Soweit korrekt?
Ich rall’s auch net -.-
Wo steht, dass man Bruteforcen soll? Ich teile meine Liste auf, bis sie nurnoch aus einem(1) oder zwei(2) punkten besteht. Da berechne ich den Abstand. Bruteforcen (also den Abstand berechnen) bei zB. 4 Punkten mach ich nicht.
Keinen Plan -.- Brauch auch Hilfe. Versteh auch die Angabe nicht…
Also mein Code:
- unteresTeilergebnis, oberesTeilergebnis mergen
- filter auf der gesamtgermergten liste aufrufen
- auf der von filter ausgespuckten liste im Abstand delta (bzw. delta’) nach neuen Punkten suchen
Aber das funzt nicht… Wie gesagt, ich verstehe eigentlich nichtmal wie der Algorithmus gehen soll-.-
1 Like
Genau. Siehe Folie 7-45. Das bringt unterm Strich die beste Performance. Ob man das dann in der Praxis so macht,
kommt aufs Problem drauf an ;).
Wieso? Du solltest einen Threshold wählen, der genügend forks zulässt damit sich der Threadpool lohnt.
Andererseits sollte der Threshold eben größer sein als 2, damit nicht für ein winziges Problem ein extra RecursiveTask erstellt wird.
Jetzt brauchst du eben einen Pi * Daumen wert dafür. Was würdest du nehmen ohne zu messen? Eine Konstante?
Ein x-tel der ursprünglichen Problemgröße wär sicher sinnvoll. Das x kann man dann auch noch abhängig vom
Parallelisierungsgrad machen, schadet nicht ;).
Beim reinen Divide-and-Conquer-Algorithmus sind die Abbruchfälle ein bzw. zwei Punkte (letzteren kann man sich theoretisch auch sparen). Bei zwei Punkten ist das Paar der nächsten Punkte trivial. Bei einem Punkt gibt es kein Paar, also ist der Abstand maximal (z.B. [m]Double.MAX_VALUE[/m]). Für beide Fälle gibt es bereits Konstruktoren in [m]ClosestPairResult[/m].
Nein, die Liste ist zwar in y-Richtung sortiert, das heißt aber nicht, dass zwei nacheinander in der Liste stehende Punkte den geringsten Abstand haben. Es geht hier ja nicht um einen geringeren Abstand in y-Richtung, sondern darum, zwei Punkte zu finden, die den geringsten euklidischen Abstand zueinander haben. Das heißt, es reicht nicht, nur zwei benachbarte Punkte zu vergleichen.
Vergesst auch nicht, eure mit [m]merge()[/m] berechnete Liste wieder in [m]ySortedListOfPoints[/m] des Ergebnisses zu speichern.
2 Likes
Müssen bzw. sollten wir für unsere RecursiveTasks in Teilaufgabe d) ein “static final serialVersionUID field of type long” deklarieren oder können wir das ignorieren?
Ich nehme an, du kommst wegen einer Warnung von Eclipse darauf. Diese Warnung wird angezeigt, weil RecursiveTask das Serializable-Interface implementiert, das es ermöglicht, eine Instanz einer Klasse in eine Datei zu schreiben. Da es aber niemanden bei dieser Aufgabe interessiert, ob man ein Arbeitspaket in eine Datei schreiben kann oder nicht, könnt ihr das bei dieser Aufgabe ignorieren (z.B. mit der Annotation [m]@SuppressWarnings(“serial”)[/m]).
Ok, hatte da was in den sheets zu closest-pair gelesen. Dürfte in meinem Fall aber leider nicht der Grund für den Fehler sein 
Du hast vollkommen recht, ich bin davon ausgegangen, dass nur nachbars-paare in y-Richtung < Delta auseinander liegen können. Aber das ist natürlich Käse 
Man muss schon so lang weiter Delta berechnen bis der Abstand in y-Richtung nicht mehr < Delta ist. Das dürfte mein Problem beheben!
edit: Wohl doch nicht behoben. SimpleSmallValueTest bricht meistens ab (ca. 80% der Fälle würd ich sagen), irgendwo zwischen 5 und 19 Punkten. Der Fehler kann bis zu 1.1 ca. auseinanderliegen.
DivideAndConquerPerfomanceTest läuft hingegen problemlos durch. Ich werd noch wahnsinnig hier… Würd ja gern meinen Code hier reinstellen, aber ich glaub das wär ne schlechte Idee 
Hier noch n kleiner Filter-Test falls den jemand verwenden möchte:
@Test
public void SimpleFilterTest(){
SimplePoint[] points = {new SimplePoint(1,0.258), new SimplePoint(10,10), new SimplePoint(20,20),new SimplePoint(2,0.16654)};
ClosestPairDivideAndConquer finder = new ClosestPairDivideAndConquer();
ArrayList<SimplePoint> yPoints = new ArrayList<SimplePoint>();
yPoints.add(points[0]);
yPoints.add(points[3]);
yPoints.add(points[1]);
yPoints.add(points[2]);
ArrayList<SimplePoint> result = new ArrayList<SimplePoint>();
result = finder.filter(yPoints, new SimplePoint(5, 1), 12);
for (int i = 0; i < result.size(); i++){
System.out.println("Punkt " +i+ ": ("+result.get(i).x+","+result.get(i).y+")" );
}
yPoints.remove(3);
assertEquals(result, yPoints);
}Die Ausgabe ist optional.
Ich find einfach meinen Fehler im Algorithmus nicht… Interessanterweise failen nur SimpleValueTest und ParallelPerformanceTest bei den result-asserts. Die anderen laufen problemlos durch. Ob das nur Glück ist? Ich weiß es nicht mehr.
Bekommt man 0 Punkte auf die Abgabe wenn nicht alle given Testcases durchlaufen?