Laufzeit P8

Benutzeravatar
Wang Tang
Mausschubser
Mausschubser
Beiträge: 92
Registriert: 5. Dez 2006 17:57

Beitrag von Wang Tang » 29. Jun 2007 00:19

hm, wenn ich nicht schon passed hätte, hätte ich ja mal Bogosort eingebaut um zu sehen, ob das passed ;)

EisNerd
Mausschubser
Mausschubser
Beiträge: 53
Registriert: 18. Nov 2005 19:54
Wohnort: Heppenheim

Beitrag von EisNerd » 29. Jun 2007 10:22

na denn:
Sorted: 200000 doubles
Time of Proxmapsort was:
188 ms
Time of my n log n was:
657 ms

Sorted: 200000 strings
Time of Proxmapsort was:
339 ms
Time of my n log n was:
638 ms

single threaded auf coreduo T2500 2*2ghz 2MB cache 2GB ram ohne vm optionen Java 1.6.0.1
Zuletzt geändert von EisNerd am 29. Jun 2007 14:35, insgesamt 1-mal geändert.
... und morgen gehts weiter.

jno
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 144
Registriert: 18. Mai 2007 09:41

Beitrag von jno » 29. Jun 2007 12:15

Ich denke, wenn man zum Ziel hat Collections.Sort() zu schlagen, muss man wohl auf jeden Fall einen Algorithmus mit n*log(n)-Laufzeit für die Bucket-Sortierung wählen, habe selbst InsertionSort genommen, der hat natürlich keine Chance. Habe allerdings auch mal spaßeshalber Collections.Sort() gegen ProxmapSort mit Collections.Sort() für die Buckets antreten lassen. Bei Doubles ist PMS auch tatsächlich ca. doppelt so schnell, bei Strings bleibt MergeSort aber deutlich schneller, keine Ahnung wieso...

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

Beitrag von HolgerF » 29. Jun 2007 12:21

Na, weil ein fairer Vergleich für Strings etwas schwierig ist. Du musst ja nach Aufgabenstellung bei ProxmapSort den String nach lower-case konvertieren und jedes Zeichen auf Gültigkeit prüfen. Das frisst ohne Ende Zeit, und Collections.sort oder sonstige Algorithmen machen das üblicherweise natürlich nicht ;)

Was InsertionSort vs. QuickSort angeht: Das kommt darauf an, für welche Sortiermengen man optimieren will. Ich hab mal meine InsertionSort und QuickSort verglichen, bis etwa 10 Elemente ist InsertionSort schneller, dann übernimmt QuickSort die Führung. Wenn du also Mengen zum Sortieren wählst, bei denen die durchschnittliche Befüllung eines Buckets unter 10 liegt (bei 100 Buckets also insgesamt < 1000 Elemente), dann ist ProxmapSort mit InsertionSort schneller als mit QuickSort (natürlich hängt der konkrete Übergang von den jeweiligen Implementierungen ab).

EisNerd
Mausschubser
Mausschubser
Beiträge: 53
Registriert: 18. Nov 2005 19:54
Wohnort: Heppenheim

Beitrag von EisNerd » 29. Jun 2007 14:32

mal zum vergleich das bringt Collections.Sort():

Sorted: 200000 doubles
Time of Proxmapsort with Collection.sort() was:
102 ms
Time of Collection.sort() was:
137 ms

Sorted: 200000 strings
Time of Proxmapsort with Collection.sort() was:
259 ms
Time of Collection.sort() was:
223 ms

Und das sind meine besten Werte mit dem was ich bis jetzt habe:

Sorted: 200000 doubles
Time of Proxmapsort was:
150 ms
Time of my n log n was:
424 ms

Sorted: 200000 strings
Time of Proxmapsort was:
325 ms
Time of my n log n was:
627 ms

single threaded auf coreduo T2500 2*2ghz 2MB cache 2GB ram ohne vm optionen Java 1.6.0.1
... und morgen gehts weiter.

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

Beitrag von vwm » 29. Jun 2007 20:27

Eieiei!
Ich hab da mal ne bescheidene Frage!
Mein Problem ist grad, dass mein ProxmapSort (mit Quicksort) zwar ganz gut funktioniert, aber dummerweise für jede Eingabe weitaus langsamer ist, als der verwendete Quicksort.
Die Quelle für diesen Unfug scheint mir das verteilen der Werte aus der ArrayList in ihre Buckets zu sein, was im Mittel nur unerheblich weniger Zeit als das Sortieren selbst in Anspruch nimmt. Das Zusammenfügen der Buckets haut dann nochmal nen Klumpen an den Fuß.
Überseh ich da irgendwas? Ich iteriere momentan beim Einlesen über die Liste und schaufel alle Elemente in ihre Buckets. Dann wende ich auf die einzelnen Buckets nacheinander einen nlogn Sortieralgorithmus an, und anschließend führe ich alle sortierten Buckets einer ArrayList mittels addAll(ArrayList) hinzu. Das Ergebnis ist sortiert, aber in jedem Fall langsamer als der Quicksort an sich.
Überprüft hab ich das ganze mit ArrayLists aus 10 bis 1200000 Zufallszahlen (Double).

Talos
Windoof-User
Windoof-User
Beiträge: 30
Registriert: 29. Apr 2004 14:03
Kontaktdaten:

Beitrag von Talos » 29. Jun 2007 22:57

Bei mir ist es so das ich Doubles ca. doppelt so schnell sortiert bekomme wie Collection.sort aber bei Strings hab ich keine Chance...Dabei ist der Algrithmus bis auf das Prüfen auf ungültige Zeichen (via Regexp, sollte also schnell gehen) und das konvertieren in kleine Zeichen identisch. Übrigens nutze ich einen Heap-Sort.

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

Beitrag von HolgerF » 30. Jun 2007 02:20

@vwm: Ist evtl. auch eine Frage, wie du über die Elemente iterierst. Benutzt du eine for-loop über eine Zählervariable i und rufst dann ArrayList.get jeweils auf? Oder benutzt du das foreach-Konstrukt (also for (elem : arrayList))? Letzteres dürfte ein bisschen schneller sein, kann aber nicht sagen, ob das jetzt den Riesenunterschied macht...

@Talos: Du musst aber eben den String vollständig prüfen UND in Kleinbuchstaben konvertieren. Das ist im Prinzip eine zweifache Iterierung über alle Chars in den Strings plus eine Copy-Operation für das Konvertieren, weil Strings immutable sind. Eigentlich müsstest du dasselbe in die Zeitmessung vor den Heapsort auch packen, damit du überhaupt eine faire Ausgangsbasis hast. Das macht schon massiv was aus.
Regex ist für diese Prüfung im Übrigen wohl auch eher langsamer als schneller (dafür natürlich kürzer zu schreiben).

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

Beitrag von vwm » 30. Jun 2007 15:50

Dass es an der Iterationsweise lag, war ja klar, aber danke für den Hinweis mit der erweiterten for-Schleife :) Ich hatte ein ähnliches Konstrukt benutzt: in etwa for (Iteratordeklaration, hasNext()) und im Körper dann next().
Bilanz auf meinem Rechner:
1. Variante: wie eben beschrieben.
2. Variante: toArray() und dann mittels Zählervariable iterieren
3. Variante: for(Object o : list)

Der 2. Ansatz stellst sich als insgesamt brauchbarster heraus (vorausgesetzt, man schaut nicht auf die Specherintensität).
Für die Speicherfreunde ist der erste zwischen 1000 und 50.000 die erste Wahl und der dritte zwischen 1 und 1000. nach 50.000 nehmen sich der erste und der dritte Ansatz nicht mehr viel.

Das sind natürlich nur meine Messungen, aber da man bei der implementierung nicht viel falsch machen konnte, geh ich mal davon aus, dass die legitim sind (über 200 Durchläufe pro Varainte und Eingabegröße gemittelt).

Jetzt wollen wir doch mal schaun, was sich damit anfangen lässt.

banshee
Nerd
Nerd
Beiträge: 684
Registriert: 22. Okt 2006 18:46

Beitrag von banshee » 3. Jul 2007 12:14

Ich werd irgendwie das Gefühl nicht los, dass etwas nicht mit dem Quicksort-Algo von den Vorlesungsfolien stimmt. Zum einen müssen hier

Code: Alles auswählen

while ((s [i] <= p) && (i <= j)) i++;
while ((s [j] > p) && (j >= i)) j--;
die beiden Bedinungen vertauscht werden, sonst kriegt man ne NullPointerException und zum andern bekomme ich schon bei 10000 Zahlen einen StackOverflow oO

Christoph B
Computerversteher
Computerversteher
Beiträge: 370
Registriert: 15. Okt 2006 18:28
Wohnort: Wiesbaden
Kontaktdaten:

Beitrag von Christoph B » 3. Jul 2007 12:53

ya, dazu gabs schon nen post im Forum zur Vorlesung wennsch mich net irre
musste den auch mehr oda weniger selbst schreiben :S

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

Beitrag von vwm » 3. Jul 2007 17:26

Wenn du die Bedingungen vertauschst, musst du aufpassen, dass du das Pivot nicht mehr mit s[j] tauschst, sondern mit s, und desweiteren, dass i in dem fall nicht außerhalb deines Arrays steht.
Was den Stackoverflow angeht: Hast du das Pivotelement aus den weiteren Rekursionsschritten ausgeschlossen? Wenn man das vergisst, kommt es bei mindestens zwei identischen zu sortierenden Werten zu einer Endlosschleife.
a tiger can smile
a snake will say it loves you
lies make us evil

banshee
Nerd
Nerd
Beiträge: 684
Registriert: 22. Okt 2006 18:46

Beitrag von banshee » 3. Jul 2007 18:33

Ich hab jetzt einfach den Quicksort-Algo genommen, wie ich ihn noch aus der Schule kannte, jetzt gehts.

banshee
Nerd
Nerd
Beiträge: 684
Registriert: 22. Okt 2006 18:46

Beitrag von banshee » 5. Jul 2007 11:39

also ich verstehe nicht wie proxmapsort langsamer sein kann als nlogn. ich benutze die identische implementierung meiner nlogn in proxmapsort und bis auf wenn 1000 elemente sortiert werden ist proxmapsort immer langsamer als quicksort. davon abgesehen is das proxmapsort mit strings immer gut und gerne 2-4mal langsamer als das mit doubles.

ich dachte der worst case von proxmapsort ist, dass er nur ein bucket hat und das dann mit nlogn sortieren muss. dann kann es aber doch wohl schlecht langsamer sein...

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

Beitrag von HolgerF » 5. Jul 2007 11:46

Folgende Überlegungen solltest du berücksichtigen:
- Proxmapsort sortiert nicht in-place, sondern verschiebt erst Elemente in Buckets und dann die Buckets zu einer neuen zusammengesetzten Liste
- Die Buckets wie auch die finale Liste müssen erzeugt und gefüllt werden
- die jeweiligen Bucketlängen sind nicht vorab bekannt, also könnten Listenvergrößerungen mit entsprechenden Reallokierungen notwendig werden
- die Überprüfung der gültigen Eingaben nimmt zusätzliche Zeit in Anspruch, ganz besonders bei den Strings, die konvertiert und Zeichen für Zeichen geprüft werden müssen

Damit sollte klar sein, dass ProxmapSort im worst case langsamer ist, einfach wegen des zusätzlichen Aufwands. Und bei Strings ist der Aufwand auch krass genug, dass er selbst im best case vermutlich keine Chance hat.
Doubles im best case kann man aber ohne weiteres schlagen, solange die doubles uniform im Gebiet von 0 bis 100 verteilt sind (Random.nextDouble() * 100). Man braucht allerdings >= 100 Elemente, weil sonst auch wieder der obige Aufwand die Performance runterzieht.

Antworten

Zurück zu „Archiv“