wo Praktikumsmaterial

Benutzeravatar
DerWildeKaiser
Windoof-User
Windoof-User
Beiträge: 28
Registriert: 16. Jan 2008 12:29

Re: wo Praktikumsmaterial

Beitrag von DerWildeKaiser »

Code: Alles auswählen

Starting QuicksortA tests!
QuicksortA [TestFile1]: Correct order! Read Ops: 3406; Write Ops: 690
19ms
QuicksortA [TestFile2]: Correct order! Read Ops: 20952; Write Ops: 0
1ms
QuicksortA [TestFile3]: Correct order! Read Ops: 21016; Write Ops: 200
2ms
QuicksortA [TestFile16]: Correct order! Read Ops: 75064173; Write Ops: 4154206
6605ms
QuicksortA [TestFile17]: Correct order! Read Ops: 170287397; Write Ops: 6740906
14576ms
QuicksortA [TestFile18]: Correct order! Read Ops: 244073324; Write Ops: 11543336
23461ms
Correct QuicksortA sortings: 6 out of 6 tests

Starting QuicksortB tests!
QuicksortB [TestFile1]: Correct order! Read Ops: 3630; Write Ops: 728
1ms
QuicksortB [TestFile2]: Correct order! Read Ops: 2390; Write Ops: 174
1ms
QuicksortB [TestFile3]: Correct order! Read Ops: 2547; Write Ops: 364
1ms
QuicksortB [TestFile16]: Correct order! Read Ops: 57243520; Write Ops: 5094910
5835ms
QuicksortB [TestFile17]: Correct order! Read Ops: 122439250; Write Ops: 8471412
10896ms
QuicksortB [TestFile18]: Correct order! Read Ops: 184334498; Write Ops: 14184178
19707ms
Correct QuicksortB sortings: 6 out of 6 tests
Testfile16 hat 500.000 Zeilen,
Testfile17 hat 800.000 Zeilen und
Testfile 18 hat 1.300.000 Zeilen
(nicht vorsortiert!)

Müssen es nur noch schaffen, dass wir bei vorsortierten Listen 0 Schreib-Operationen kriegen.

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

Re: wo Praktikumsmaterial

Beitrag von Maeher »

So letze Optimierungen gelungen:

Code: Alles auswählen

Starting QuicksortA tests!
QuicksortA [TestFile3]: Correct order! Read Ops: 20405; Write Ops: 200; ms: 15
QuicksortA [TestFile1]: Correct order! Read Ops: 2412; Write Ops: 690; ms: 0
QuicksortA [TestFile2]: Correct order! Read Ops: 20325; Write Ops: 0; ms: 3
Correct QuicksortA sortings: 3 out of 3 tests

Starting QuicksortB tests!
QuicksortB [TestFile3]: Correct order! Read Ops: 2212; Write Ops: 200; ms: 0
QuicksortB [TestFile1]: Correct order! Read Ops: 2770; Write Ops: 702; ms: 11
QuicksortB [TestFile2]: Correct order! Read Ops: 2031; Write Ops: 0; ms: 0
Correct QuicksortB sortings: 3 out of 3 tests
aufsteigend sortierte immer mit 0 write ops, absteigend sortierte immer mit n write ops für gerade und n-1 write ops für ungerade anzahl

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

Re: wo Praktikumsmaterial

Beitrag von Stumpf.Alex »

Dumme Frage, aber wieso und woher habt ihr die Anzeige der tatsächlichen Laufzeit?

Pascha
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 242
Registriert: 6. Jun 2007 14:03

Re: wo Praktikumsmaterial

Beitrag von Pascha »

Ist es erlaubt sich das Pivotelement zu merken, sprich BookID und ReaderID abzuspeichern oder soll man bei jedem Vergleich über den Index auf das Pivotelement in der Liste zugreifen?

Benutzeravatar
DerWildeKaiser
Windoof-User
Windoof-User
Beiträge: 28
Registriert: 16. Jan 2008 12:29

Re: wo Praktikumsmaterial

Beitrag von DerWildeKaiser »

Stumpf.Alex hat geschrieben:Dumme Frage, aber wieso und woher habt ihr die Anzeige der tatsächlichen Laufzeit?
So gehts das:

Code: Alles auswählen

long anfang = System.currentTimeMillis();
//Dein Code hier...
System.out.println("Laufzeit: " + System.currentTimeMillis() - anfang);
System.currentTimeMillis(); gibt die aktuelle Uhrzeit in Milisekunden zurück...

Benutzeravatar
s!mon
Computerversteher
Computerversteher
Beiträge: 373
Registriert: 20. Okt 2007 18:24
Wohnort: Höchst i. Odw

Re: wo Praktikumsmaterial

Beitrag von s!mon »

Code: Alles auswählen

Starting QuicksortA tests!
QuicksortA [TestFile1]: Correct order! Read Ops: 2377; Write Ops: 1496
QuicksortA [TestFile2]: Correct order! Read Ops: 20099; Write Ops: 0
QuicksortA [TestFile3]: Correct order! Read Ops: 30199; Write Ops: 20200
Correct QuicksortA sortings: 3 out of 3 tests

Starting QuicksortB tests!
QuicksortB [TestFile1]: Correct order! Read Ops: 2379; Write Ops: 1496
QuicksortB [TestFile2]: Correct order! Read Ops: 20101; Write Ops: 0
QuicksortB [TestFile3]: Correct order! Read Ops: 29804; Write Ops: 19802
Correct QuicksortB sortings: 3 out of 3 tests
Ist noch nicht optimiert. Wenigstens habe ich jetzt den Fehler gefunden der mich lange gequält hat und es läuft :P

Benutzeravatar
IchWarsNicht
Neuling
Neuling
Beiträge: 10
Registriert: 23. Okt 2007 15:03

Re: wo Praktikumsmaterial

Beitrag von IchWarsNicht »

Huhu ^^

Also ich will Euch ja nicht auf dumme Gedanken bringen... aber man kann die Werte ZIEMLICH heftig "tunen" :)

Schaut mal auf was für dumme Gedanken ein 6-Semester-Studi so alles kommt:

Code: Alles auswählen

Starting QuicksortA tests!
QuicksortA [TestFile1]: Correct order! Read Ops: 200; Write Ops: 690
QuicksortA [TestFile2]: Correct order! Read Ops: 200; Write Ops: 0
QuicksortA [TestFile3]: Correct order! Read Ops: 200; Write Ops: 200
Correct QuicksortATuned sortings: 3 out of 3 tests

Starting QuicksortB tests!
QuicksortB [TestFile1]: Correct order! Read Ops: 200; Write Ops: 1094
QuicksortB [TestFile2]: Correct order! Read Ops: 200; Write Ops: 0
QuicksortB [TestFile3]: Correct order! Read Ops: 200; Write Ops: 200
Correct QuicksortBTuned sortings: 3 out of 3 tests
Ich geb Euch nen Tipp: Caching!
Man kann ja durchaus argumentieren, dass das lesen vom Speicher mit den Daten teuer ist und man lieber ein bischen was in einen Cache einlagert :D
Bestimmt nicht im Sinne der Aufgabensteller :twisted:

Have fun!
Zuletzt geändert von IchWarsNicht am 11. Apr 2008 23:55, insgesamt 2-mal geändert.

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

Re: wo Praktikumsmaterial

Beitrag von Wang Tang »

Will dir ja nich den Spaß verderben, aber ich finde das is ziemlich eindeutig:
Man darf nicht temporäre Arrays benutzen, um die Anzahl der Lese und
Schreiboperationen zu reduzieren!
Unter Punkt 5 ;)

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

Re: wo Praktikumsmaterial

Beitrag von Stumpf.Alex »

Dem muss ich mich auch anschließen, weil wenn du dass alles in der Map speicherst, dann macht man ja alles Lese- und Schreiboperationen auf der Map und das verfälscht die Statistik, was ja nicht gewünscht/erlaubt ist.

Selbst ein "dummer" Zweiti würde sonst auf die Idee kommen, alles zu cachen, also so weit sind wir schon :wink: .

Benutzeravatar
Simon MD
Mausschubser
Mausschubser
Beiträge: 48
Registriert: 5. Mai 2007 12:27
Wohnort: Nieder-Ramstadt
Kontaktdaten:

Re: wo Praktikumsmaterial

Beitrag von Simon MD »

Pascha hat geschrieben:Ist es erlaubt sich das Pivotelement zu merken, sprich BookID und ReaderID abzuspeichern oder soll man bei jedem Vergleich über den Index auf das Pivotelement in der Liste zugreifen?
Ja, das kann man machen und ist erlaubt.
"Erfolg ist die Feigheit vor der eigenen Inkompetenz"
- Oliver Kalkofe -

Osterlaus
BSc Spammer
BSc Spammer
Beiträge: 1263
Registriert: 23. Aug 2007 12:46
Wohnort: DA

Re: wo Praktikumsmaterial

Beitrag von Osterlaus »

@Simon: Hast du ne Quelle dafür?

Benutzeravatar
Simon MD
Mausschubser
Mausschubser
Beiträge: 48
Registriert: 5. Mai 2007 12:27
Wohnort: Nieder-Ramstadt
Kontaktdaten:

Re: wo Praktikumsmaterial

Beitrag von Simon MD »

Naja, also mir hat das ein GdI2-Tutor gesagt und habe das auch nun schon sehr häufig hier im Forum gelesen, dass das so gemacht wurde und bisher kein Admin/Assistent/Prof etwas dagegen gesagt hat.
Zumal man das Pivotelement bei jedem rekursiven Aufruf von Quicksort eh neu einlesen muss.
Allerdings solange dann jeder einzelne Aufruf läuft nutzt man immer das gleiche Element und da macht es sinn es sich zu speichern...
"Erfolg ist die Feigheit vor der eigenen Inkompetenz"
- Oliver Kalkofe -

Benutzeravatar
Krümelmonster
Geek
Geek
Beiträge: 767
Registriert: 17. Okt 2007 13:58
Wohnort: Jossgrund

Re: wo Praktikumsmaterial

Beitrag von Krümelmonster »

Ich hatte u.A. diese Frage an die Kontaktadresse weitergeleitet.
Hier die Antwort.
Stell deinen Fuß auf einen hohen Sockel
Mach dir ein Haar aus tausend Locken
Du bleibst doch immer, was du bist!

Benutzeravatar
s!mon
Computerversteher
Computerversteher
Beiträge: 373
Registriert: 20. Okt 2007 18:24
Wohnort: Höchst i. Odw

Re: wo Praktikumsmaterial

Beitrag von s!mon »

Sacht mal gibts jetzt eigentlich ne Lösung für das StackOverFlow-Problem bei langen Testlisten? Liegt das nur daran, dass dem Stack zu wenig Speicher zugewiesen wird oder gibt es eine Implementierung (bei QuicksortA), bei der dieses Problem nicht auftritt? Oder dürfen wir diesen "Hack" benutzen (bringt ja auch nichts wenn die Tests hier laufen und dann beim Testat durchfallen)

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

Re: wo Praktikumsmaterial

Beitrag von Maeher »

Eine Möglichkeit, das Problem zu umgehen, ist den Quicksort halbiterativ zu implementieren. Das bedeutet man schickt nur die kürzere Teilliste in eine Rekursion und arbeitet die längere iterativ ab. Die Rekursionstiefe nimmt dadurch signifikant ab. Ansonsten ist zu sagen, dass es an sich nicht unbedingt dein Problem ist, es wird wahrscheinlich nicht erwartet derart lange Teillisten abzuarbeiten. Und ich schätze wenn das eben doch auftritt und du in der Lage bist zu erklären, wieso es dazu kommt (Und somit die Nachteile der Rekursion erkennst... yay^^) kann man dir da keinen Strick draus drehen.

Antworten

Zurück zu „Archiv“