Quicksort Performance

secretmojo
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 124
Registriert: 31. Jan 2007 19:30

Quicksort Performance

Beitrag von secretmojo »

Hallo Leute, wollte mal nachfragen, wie ihr die leistungssteigerung bei QuicksortB empfunden habt. Leider ist bei meine algo durch die wahl des mittleren Elements keine wirkliche perfomance-verbesserung bemerkbar.
Ansonsten gehts ja...hier mein output:

Starting QuicksortA tests!
QuicksortA [TestFile1]: Correct order! Read Ops: 5589; Write Ops: 1040
QuicksortA [TestFile2]: Correct order! Read Ops: 21124; Write Ops: 398
QuicksortA [TestFile3]: Correct order! Read Ops: 22101; Write Ops: 596
Correct QuicksortA sortings: 3 out of 3 tests

Starting QuicksortB tests!
QuicksortB [TestFile1]: Correct order! Read Ops: 6434; Write Ops: 1520
QuicksortB [TestFile2]: Correct order! Read Ops: 5732; Write Ops: 1324
QuicksortB [TestFile3]: Correct order! Read Ops: 6255; Write Ops: 1494
Correct QuicksortB sortings: 3 out of 3 tests

bei den mitgelieferten Testflile2 und Testfile3 sieht man schon eine verbesserung, aber wenn ich mir eigene Fälle generiere, dann ist da kaum ein unterschied.

Mspringer
Nerd
Nerd
Beiträge: 555
Registriert: 19. Okt 2006 14:41
Wohnort: Darmstadt / Alzenau
Kontaktdaten:

Re: Quicksort Performance

Beitrag von Mspringer »

Ich finde es sehr interessant wie du schreibzugriffe auf "sortierte!" Listen hast. Ich würde mal ein wenig drübergucken.

ChristianK
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 127
Registriert: 13. Sep 2007 01:15
Wohnort: Darmstadt
Kontaktdaten:

Re: Quicksort Performance

Beitrag von ChristianK »

naja sooo abwägig ist das nicht. Das kann schonmal passieren, dass man z.B. 1 Element an die gleiche Stelle tauscht... Hatten wir auch am Anfang...

Benutzeravatar
Maeher
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 282
Registriert: 14. Okt 2007 23:02
Kontaktdaten:

Re: Quicksort Performance

Beitrag von Maeher »

Das sollte man aber vor dem tauschen merken und dann abrechen. ;)

Dass du da wenig Steigerung siehst hat nen einfachen Grund. Bei unsortierten Listen mit normaler stochastischer Verteilung ist es schlichtweg scheißegal welches Element du wählst.
Was durch diese Auswahl verhindert wird ist die Laufzeit n^2 für sortierte Listen. Für unsortierte bringt es gemittelt auf alle Fälle keinen Vorteil (wenn auch durch das Vergleichen für die Auswahl nen kleinen Nachteil)

Mspringer
Nerd
Nerd
Beiträge: 555
Registriert: 19. Okt 2006 14:41
Wohnort: Darmstadt / Alzenau
Kontaktdaten:

Re: Quicksort Performance

Beitrag von Mspringer »

ChristianK hat geschrieben:naja sooo abwägig ist das nicht. Das kann schonmal passieren, dass man z.B. 1 Element an die gleiche Stelle tauscht... Hatten wir auch am Anfang...
Das ist mir bewusst, aber vielleicht wär er auch so drauf gekommen, weshalb ich ihm ja riet es sich nochmal anzusehen. ;)

Benutzeravatar
itportal2
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 236
Registriert: 25. Jan 2008 15:34
Wohnort: Darmstadt

Re: Quicksort Performance

Beitrag von itportal2 »

secretmojo hat geschrieben: Starting QuicksortA tests!
QuicksortA [TestFile1]: Correct order! Read Ops: 5589; Write Ops: 1040
QuicksortA [TestFile2]: Correct order! Read Ops: 21124; Write Ops: 398
QuicksortA [TestFile3]: Correct order! Read Ops: 22101; Write Ops: 596
Correct QuicksortA sortings: 3 out of 3 tests
Und du benutzst weder temporäre Arrays, noch temporäre ArraySorts? Bei mir sieht so aus:

Starting QuicksortA tests!
QuicksortA [TestFile1]: Correct order! Read Ops: 2108; Write Ops: 1225
QuicksortA [TestFile2]: Correct order! Read Ops: 20099; Write Ops: 0
QuicksortA [TestFile3]: Correct order! Read Ops: 20099; Write Ops: 20099
Correct QuicksortA sortings: 3 out of 3 tests

c_kulas
Neuling
Neuling
Beiträge: 10
Registriert: 1. Okt 2007 16:05
Kontaktdaten:

Re: Quicksort Performance

Beitrag von c_kulas »

Jetzt muss ich auch mal meinen Senf dazu geben:

QuicksortA [TestFile1]: Correct order! Read Ops: 2796; Write Ops: 758
QuicksortA [TestFile2]: Correct order! Read Ops: 20696; Write Ops: 398
QuicksortA [TestFile3]: Correct order! Read Ops: 20696; Write Ops: 398
Correct QuicksortA sortings: 3 out of 3 tests

Starting QuicksortB tests!
QuicksortB [TestFile1]: Correct order! Read Ops: 2649; Write Ops: 716
QuicksortB [TestFile2]: Correct order! Read Ops: 1640; Write Ops: 144
QuicksortB [TestFile3]: Correct order! Read Ops: 1937; Write Ops: 342
Correct QuicksortB sortings: 3 out of 3 tests

Was krieg ich nun?

Stumpf.Alex
Nerd
Nerd
Beiträge: 644
Registriert: 1. Okt 2007 12:40
Wohnort: Darmstadt
Kontaktdaten:

Re: Quicksort Performance

Beitrag von Stumpf.Alex »

Ne ollen Keks und schales Bier :wink: . Und vielleicht viele Punkte beim Testat.

c_kulas
Neuling
Neuling
Beiträge: 10
Registriert: 1. Okt 2007 16:05
Kontaktdaten:

Re: Quicksort Performance

Beitrag von c_kulas »

Bier ist immer gut. :>

Mspringer
Nerd
Nerd
Beiträge: 555
Registriert: 19. Okt 2006 14:41
Wohnort: Darmstadt / Alzenau
Kontaktdaten:

Re: Quicksort Performance

Beitrag von Mspringer »

c_kulas hat geschrieben: Starting QuicksortB tests!
QuicksortB [TestFile1]: Correct order! Read Ops: 2649; Write Ops: 716
QuicksortB [TestFile2]: Correct order! Read Ops: 1640; Write Ops: 144
QuicksortB [TestFile3]: Correct order! Read Ops: 1937; Write Ops: 342
Correct QuicksortB sortings: 3 out of 3 tests
Sicher das ihr nicht zwischenspeichert? Irgendwie kommt mir das zu krass vor.

c_kulas
Neuling
Neuling
Beiträge: 10
Registriert: 1. Okt 2007 16:05
Kontaktdaten:

Re: Quicksort Performance

Beitrag von c_kulas »

ich speichere einzelne elemente wie z.b. das pivotelement zwischen für spätere vergleiche und das ist ja nicht verboten.

secretmojo
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 124
Registriert: 31. Jan 2007 19:30

Re: Quicksort Performance

Beitrag von secretmojo »

Das finde ich persönlich auch bequemer, wobei ich es so verstanden habe, dass man überhaupt keine Elemente aus der liste in temporären arrays zwischen speichern darf. Weder pivot noch sonst ein element. Alle schreib- und lesezugriffe sollen auf die liste passieren, damit man die komplexität messen kann, denke ich.

c_kulas
Neuling
Neuling
Beiträge: 10
Registriert: 1. Okt 2007 16:05
Kontaktdaten:

Re: Quicksort Performance

Beitrag von c_kulas »

naja, das pivotelement ist zwar schon ein array, aber nicht das array was die meinten. so wie ichs verstanden hab, sollen wir halt nicht n neues array erstellen, wo alle elemente aus records unsortiert hineinkopiert werden, auf dem dann sortiert wird. aber bei einem element ... also ich weiß ja nicht.. :/

*edit
mein temporäres array pivotelement ist nur ne referenz aufs originale, also wirds nirgends zwischengespeichert.

Benutzeravatar
Twister11
Mausschubser
Mausschubser
Beiträge: 48
Registriert: 26. Nov 2005 14:18
Kontaktdaten:

Re: Quicksort Performance

Beitrag von Twister11 »

Kannst du mal nen Tipp geben wie du auf deine kranken Ergebnisse kommst?
Bin mit meinen auch schon ganz gut dabei denk ich mal...

Starting QuicksortA tests!
QuicksortA [TestFile1]: Correct order! Read Ops: 3228; Write Ops: 774
QuicksortA [TestFile2]: Correct order! Read Ops: 20895; Write Ops: 0
QuicksortA [TestFile3]: Correct order! Read Ops: 20993; Write Ops: 200
QuicksortA [TestFileEDCBA]: Correct order! Read Ops: 43; Write Ops: 2
Correct QuicksortA sortings: 4 out of 4 tests

Starting QuicksortB tests!
QuicksortB [TestFile1]: Correct order! Read Ops: 4454; Write Ops: 746
QuicksortB [TestFile2]: Correct order! Read Ops: 8985; Write Ops: 0
QuicksortB [TestFile3]: Correct order! Read Ops: 9243; Write Ops: 200
QuicksortB [TestFileEDCBA]: Correct order! Read Ops: 67; Write Ops: 2
Correct QuicksortB sortings: 4 out of 4 tests

Aber deine sind echt abnormal!!!!! :P

tmx-master
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 253
Registriert: 25. Okt 2006 17:44

Re: Quicksort Performance

Beitrag von tmx-master »

secretmojo hat geschrieben:Hallo Leute, wollte mal nachfragen, wie ihr die leistungssteigerung bei QuicksortB empfunden habt. Leider ist bei meine algo durch die wahl des mittleren Elements keine wirkliche perfomance-verbesserung bemerkbar.
Ansonsten gehts ja...hier mein output:

Starting QuicksortA tests!
QuicksortA [TestFile1]: Correct order! Read Ops: 5589; Write Ops: 1040
QuicksortA [TestFile2]: Correct order! Read Ops: 21124; Write Ops: 398
...
Hi zusammen,
also was man fordern kann, ist, dass beim QuicksortA für das TestFile2 die Write Ops gleich 0 sein müssten. Die Liste ist ja schon aufsteigend sortiert und ohne "gleiche Elemente" ausgestattet. Hier sollten also keine Vertauschoperationen (was ja immer mit 2 setElementAt(index)-Aufrufen verbunden ist) stattfinden.
Ob das bei QuickSortB so einfach gelingt ist fraglich, da man ja ggf. das gefundene Pivottelement irgendwie in records platzieren will / muss. Twister hat aber gezeigt, dass man das auch ohne Neuplatzierung schaffen kann. Ok, wir arbeiten dran... :)
Gruß TM

Antworten

Zurück zu „Archiv“