Laufzeit P8

moFries
Erstie
Erstie
Beiträge: 17
Registriert: 2. Mai 2007 13:09
Kontaktdaten:

Laufzeit P8

Beitrag von moFries » 28. Jun 2007 10:21

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?

Benutzeravatar
vwm
Mausschubser
Mausschubser
Beiträge: 94
Registriert: 7. Mai 2007 09:42
Wohnort: Rodenbach

Beitrag von vwm » 28. Jun 2007 10:41

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.
a tiger can smile
a snake will say it loves you
lies make us evil

moFries
Erstie
Erstie
Beiträge: 17
Registriert: 2. Mai 2007 13:09
Kontaktdaten:

Beitrag von moFries » 28. Jun 2007 11:04

so hab ich es jetzt mal gemacht, leider ist die aussagekraft bei kleinen mengen unnütz.

Benutzeravatar
Gnomix
Computerversteher
Computerversteher
Beiträge: 306
Registriert: 31. Okt 2005 08:44

Beitrag von Gnomix » 28. Jun 2007 11:25

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.

Benutzeravatar
m0ep
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 189
Registriert: 5. Okt 2006 22:52
Wohnort: Bensheim
Kontaktdaten:

Beitrag von m0ep » 28. Jun 2007 11:44

Ich würde sagen es reicht die Laufzeit für ein paar Mengen an Zufallszahlen zu messen ....

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

: |

HolgerF
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 263
Registriert: 16. Jan 2007 14:20
Kontaktdaten:

Beitrag von HolgerF » 28. Jun 2007 11:51

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.

Benutzeravatar
Skullz
Mausschubser
Mausschubser
Beiträge: 44
Registriert: 23. Mai 2007 16:21

Beitrag von Skullz » 28. Jun 2007 16:48

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?

Azadi
Windoof-User
Windoof-User
Beiträge: 30
Registriert: 28. Sep 2006 09:51

Beitrag von Azadi » 28. Jun 2007 17:31

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 :)

Benutzeravatar
Skullz
Mausschubser
Mausschubser
Beiträge: 44
Registriert: 23. Mai 2007 16:21

Beitrag von Skullz » 28. Jun 2007 19:15

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

HolgerF
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 263
Registriert: 16. Jan 2007 14:20
Kontaktdaten:

Beitrag von HolgerF » 28. Jun 2007 19:28

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.

Benutzeravatar
Skullz
Mausschubser
Mausschubser
Beiträge: 44
Registriert: 23. Mai 2007 16:21

Beitrag von Skullz » 28. Jun 2007 19:39

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. :-(

HolgerF
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 263
Registriert: 16. Jan 2007 14:20
Kontaktdaten:

Beitrag von HolgerF » 28. Jun 2007 19:45

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

HolgerF
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 263
Registriert: 16. Jan 2007 14:20
Kontaktdaten:

Beitrag von HolgerF » 28. Jun 2007 20:41

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.

maikg2
Mausschubser
Mausschubser
Beiträge: 95
Registriert: 18. Okt 2005 22:29
Wohnort: Darmstadt

Beitrag von maikg2 » 28. Jun 2007 20:54

Cool, ich brauch mir nun überhaupt keine Gedanken mehr machen. Danke Holger (und dem Rest natürlich auch)......

RomanSoldier
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 220
Registriert: 1. Dez 2005 20:32

Beitrag von RomanSoldier » 29. Jun 2007 00:00

Collection.sort hat Mergesort implementiert - einer der effizientesten Sortieralgorithmen überhaupt. Meiner schlägt ihn dennoch :D

Antworten

Zurück zu „Archiv“