Seite 1 von 3

Laufzeit P8

Verfasst: 28. Jun 2007 10:21
von moFries
Ich bin ein wenig verwirrt von der Aufgabenstellung:
Lassen Sie Ihre Implementierung gegen einen Sortieralgorithmus in n log n antreten
und vergleichen Sie die Laufzeiten für verschieden große Eingabemengen (kleine bis
sehr große). Sie müssen dazu keine umfangreiche Statistik anfertigen, einige Werte
dürften ausreichen.
Das bedeutet, wir sollen noch einen n log n (z.B. QuickSort) schreiben, aber wie soll ich die Laufzeit miteinander vergleichen. Soll ich Counter in die Sortieralgorithmen einbauen, oder was?

Verfasst: 28. Jun 2007 10:41
von vwm
Merk dir die System.currentTimeMillis(), sortiere mit "Proxmap", gib die vergangene Zeit aus, merk dir die aktuelle System.currentTimeMillis(), sortiere mit Irgendwas-nlogn-Sort und gib wieder die Zeitdifferenz aus. Voilá. Das machst du (mehrmals) für ein paar deutlich verschieden große Eingaben und schreibst die Ergebnisse zusammen mit der Eingabegröße auf.

Verfasst: 28. Jun 2007 11:04
von moFries
so hab ich es jetzt mal gemacht, leider ist die aussagekraft bei kleinen mengen unnütz.

Verfasst: 28. Jun 2007 11:25
von Gnomix
Oder du überlegst dir welche Operationen Kritisch sind, und baust einen Zähler ein, der ihre Anzahl ermittelt.
Diesen gibst du dann nach jedem Sortieren aus, und fertig.
Oder du gibst ein Verhältnis aus.

Verfasst: 28. Jun 2007 11:44
von m0ep
Ich würde sagen es reicht die Laufzeit für ein paar Mengen an Zufallszahlen zu messen ....

also für 100 1000 10000 ......

: |

Verfasst: 28. Jun 2007 11:51
von HolgerF
Denkt aber dran (falls ihr Laufzeiten messt), gerade bei kleineren Werten die Sortierung in einer Schleife oft durchzuführen und die Gesamtzeit dann durch die Wiederholungen zu teilen (also Mittelwert), ansonsten könnt ihr den Wert ziemlich vergessen.

Verfasst: 28. Jun 2007 16:48
von Skullz
Mal so 'ne Frage zur Laufzeit?

Habt ihr da auch irgendwie das Ergebnis, dass euer ProxmapSort generell länger braucht als der n*log n-Sort?

Verfasst: 28. Jun 2007 17:31
von Azadi
Ja bei mir verhält es sich auch so. Erst bei der Sortierung von 1000000 Zahlen ist der Proxmap mininal schneller als mein Quicksort. Irgendwie hatte ich mir das anders vorgestellt :)

Verfasst: 28. Jun 2007 19:15
von Skullz
Über so ein Ergebnis würde ich mich ja freuen, aber so sieht's bei mir wirklich nicht aus.
Bei 1.000.000 Doubles ist der QuickSort sehr deutlich schneller (2782 Millis bei QuickSort und 3968 Millis bei ProxmapSort).
Keine Ahnung woran es liegt. Naja... Hauptsache das Testatsystem läuft durch...

Ach, und bei Strings hört der Spaß ganz auf.

Verfasst: 28. Jun 2007 19:28
von HolgerF
Für 1.000.000 Doubles ist der ProxmapSort eigentlich auch gar nicht ausgelegt. Das Verfahren wird eigentlich dann am stärksten, wenn die Buckets möglichst wenige Elemente enthalten, also wenn die Anzahl der Elemente ungefähr in der Größenordnung der Anzahl Buckets liegt und möglichst gleichverteilt sind. In diesem Fall sollte ProxmapSort mit einem möglichst simplen Sortierverfahren (z. B. InsertionSort) eigentlich die nlogn Bande schlagen können.
Wenn die Anzahl Elemente zunehmen und sich die Buckets füllen, dann begrenzt aber zunehmend der von Proxmap verwendete Sortieralgorithmus wieder, und dann dürfte Quicksort schon aus Einfachheit das Rennen gewinnen.

Verfasst: 28. Jun 2007 19:39
von Skullz
Also in der Aufgabenstellung steht, dass wir einen beliebigen Sortieralgorithmus zum Sortieren der Buckets nutzen sollen. Dementsprechend hab ich da halt auch den QuickSort benutzt, weil ich den ja sowieso schon für die Extra-Tests implementieren musste.

Das mit der Belegung ist klar, nur habe ich nicht mit so einem deutlichen Ergebnis gerechnet und sicherheitshalber mal gefragt.
Leider ist es halt so, dass sich die kleinen Zahlenbereiche, in denen der ProxmapSort besser sein sollte, kaum sinnvoll testen lassen, weil die Zeitmessung für die geringe Anzahl an Buckets doch sehr vage ist. Von daher muss ich wohl damit leben, nicht deutlich zu sehen, dass sich der Aufwand für den ProxmapSort im Vergleich zum QuickSort gelohnt hat. :-(

Verfasst: 28. Jun 2007 19:45
von HolgerF
Nein, du musst bloß die Sortierung zigmal ausführen, z. B. 1000x eine zufällige ArrayList erstellen, dann die Millisekunden (oder sogar Nanosekunden) für den Sortiervorgang dieser Liste messen und diese Zeit auf ein Gesamtkonto aufschlagen. Dann kannst du am Ende sehr gut die Gesamtzeiten vergleichen.

Ich hab im Übrigen mittlerweile den Double-Teil fertig und gerade spaßeshalber mal gegen Collections.sort antreten lassen (hab bislang nur InsertionSort umgesetzt). Kurioserweise hat mich der Test gerade gleich Lügen gestraft.
Bei 100 Elementen war Collections.sort noch schneller, aber von 400 bis 400.000 Elementen hat mein ProxmapSort nur 1/2 bis 1/3 so viel Zeit gebraucht oO. Aber ok, Collections.sort ist ja auch ein MergeSort, das ist natürlich trotz guter asymptotischer Laufzeit recht teuer.
Naja, mal sehen, wie das gegen einen eigenen QuickSort aussieht und wie sich Proxmap verhält, wenn ich QuickSort statt InsertionSort verwende...

Verfasst: 28. Jun 2007 20:41
von HolgerF
War wohl ein bisschen voreilig, heh. In meinem InsertionSort war ein dämlicher Fehler, so dass er meistens gar nicht wirklich sortiert hat - klar, dass er dann bei großen Eingaben deutlich schneller ist.

Der Fehler ist aber korrigiert und QuickSort eingebaut. QuickSort kommt zwar an Collections.sort dann doch nicht ganz ran (war aber *eigentlich* auch zu erwarten, das Ding ist zweifellos böse optimiert). Mit InsertionSort ist ProxmapSort bei mir so zwischen 200 und 4000 Elementen schneller als Quicksort, danach gewinnt Quicksort die Oberhand (darunter teilweise auch, da ist das Einsortieren und Verbinden der Buckets halt zu aufwendig). Wenn ich Proxmap mit Quicksort verwende, gewinnt Proxmap auch noch bei 10000 Elementen gegen das einfache Quicksort, das hab ich dann noch nicht weiter getestet.

Verfasst: 28. Jun 2007 20:54
von maikg2
Cool, ich brauch mir nun überhaupt keine Gedanken mehr machen. Danke Holger (und dem Rest natürlich auch)......

Verfasst: 29. Jun 2007 00:00
von RomanSoldier
Collection.sort hat Mergesort implementiert - einer der effizientesten Sortieralgorithmen überhaupt. Meiner schlägt ihn dennoch :D