Algorithmen[Prog1]
Algorithmen[Prog1]
Hallo,
wie schnell ist denn euer Algorithmus?
Ich habe gerade den Algorithmus fertig geschrieben und frage mich, wie schnell der Algorithmus eigentlich sein soll.
Meiner arbeitet in-place und funktioniert soweit auch (getestet auf vielen kleinen Arrays). Das SortingFramework (Random) rechnet jetzt aber schon gefühlte 10 Minuten ohne Ergebnis.
Dauert das bei euch auch so lange, oder ist meine implementierung einfach nur zu schlecht?
wie schnell ist denn euer Algorithmus?
Ich habe gerade den Algorithmus fertig geschrieben und frage mich, wie schnell der Algorithmus eigentlich sein soll.
Meiner arbeitet in-place und funktioniert soweit auch (getestet auf vielen kleinen Arrays). Das SortingFramework (Random) rechnet jetzt aber schon gefühlte 10 Minuten ohne Ergebnis.
Dauert das bei euch auch so lange, oder ist meine implementierung einfach nur zu schlecht?
Re: Algorithmen[Prog1]
Auf einem T7200 (Core 2 Duo mit 2*2Ghz) braucht der Benchmark bei mir ungefähr ne Minute, vielleicht auch zwei ...
Und wie schnell mein Algorithmus ist: Im Schnitt zwischen dem mitgelieferten Quicksort und dem JDK-Quicksort.
mfG
Markus
Und wie schnell mein Algorithmus ist: Im Schnitt zwischen dem mitgelieferten Quicksort und dem JDK-Quicksort.
mfG
Markus
Re: Algorithmen[Prog1]
Danke, habe gesehen, dass ich einen Fehler habe. Große Bereiche des Arrays wurden öfters sortiert, weil ich einen falschen Index übergeben hatte.
Re: Algorithmen[Prog1]
Leute, es gibt etwas in der Aufgabestellung die ich nicht verstanden habe: was ist der Zusammenhang zw. sort und presortedPrefixSort? Danke!
Re: Algorithmen[Prog1]
@jcdmb
Schau mal in der Quicksort-Datei, dort sind auch 2 ähnliche Funktionen. Die eine ruft die andere einfach mit den richtigen Parametern auf.
Nochmal zum Graphen:
Soll es so "wellig" sein wie bei Nidan? Bei mir sieht es so aus:
http://i41.tinypic.com/16bd2k8.jpg
Schau mal in der Quicksort-Datei, dort sind auch 2 ähnliche Funktionen. Die eine ruft die andere einfach mit den richtigen Parametern auf.
Nochmal zum Graphen:
Soll es so "wellig" sein wie bei Nidan? Bei mir sieht es so aus:
http://i41.tinypic.com/16bd2k8.jpg
Re: Algorithmen[Prog1]
Nidan: Meiner ist auch recht "wellig", analog zu dir gibt es dort ein Dreiecksmuster dass ziemlich genau periodisch zum Exponenten modulo 4 ist.
salami: Hey, tolle Implementierung, so ähnlich sehen meine Ergebnisse auch aus.
mfG
Markus
salami: Hey, tolle Implementierung, so ähnlich sehen meine Ergebnisse auch aus.
mfG
Markus
Re: Algorithmen[Prog1]
Hier auch meine Ergebnisse Pro Test etwa 20 Sekunden auf Intel Core 2 Duo T5750 @ 2.0 GHz
Ich verstehe nur nicht, warum QuickSort sich so seltsam verhält bei mir im Vergleich zu den anderen Bildern im Forum
Presorted
Random
Nach einer kleiner Optimierung (vor der eigentlichen Bearbeitung, den Argumenten s so viel wachsen lassen wie möglich). Ich werde meinen Tutor fragen, ob das erlaubt ist (weil es ja abweicht von der Aufgabenstellung).
Presorted Optimized
Random Optimized
Ich kann mich nur wundern wie salami es "ganz unter" QuickSort im zufälligen Fall gebracht hat Vielleicht fällt mir gerade nicht ein, wie man die Wellenberge unterdrücken kann...
Habt ihr (und sollen wir) mit anderen Werten für p experimentieret?
Ich verstehe nur nicht, warum QuickSort sich so seltsam verhält bei mir im Vergleich zu den anderen Bildern im Forum
Presorted
Random
Nach einer kleiner Optimierung (vor der eigentlichen Bearbeitung, den Argumenten s so viel wachsen lassen wie möglich). Ich werde meinen Tutor fragen, ob das erlaubt ist (weil es ja abweicht von der Aufgabenstellung).
Presorted Optimized
Random Optimized
Ich kann mich nur wundern wie salami es "ganz unter" QuickSort im zufälligen Fall gebracht hat Vielleicht fällt mir gerade nicht ein, wie man die Wellenberge unterdrücken kann...
Habt ihr (und sollen wir) mit anderen Werten für p experimentieret?
When we say that two functions are almost always used together, we should remember that "almost" is a euphemism for "not."
-- David L. Parnas, "Designing Software for Ease of Extension and Contraction"
-- David L. Parnas, "Designing Software for Ease of Extension and Contraction"
Re: Algorithmen[Prog1]
Nachdem ich meinen Algorithmus weiter "optimiert" habe, habe ich jetzt auch diese Wellenmuster drin.
Leider habe ich kein Backup gemacht, so dass ich jetzt nicht mehr zurück zum anderen Algo komme.
Egal. Die Wellenmuster kommen [bei mir] so zustande, dass an diesen Stellen sr viel größer ist als ul. Deshalb müssen mehr Kopieroperationen ausgeführt werden, was zu längeren Laufzeiten führt.
Hier mein Algo jetzt:
http://i44.tinypic.com/1zfs9d1.png
Da bei Mergesort hat Java wohl gerade einen Cache geleert oder gefüllt. Anders kann ich mir diese Ausreißer nicht erklären. Die treten immer wieder mal bei verschiedenen Algorithmen auf.
PS: Das mit dem s erhöhen habe ich auch.
Leider habe ich kein Backup gemacht, so dass ich jetzt nicht mehr zurück zum anderen Algo komme.
Egal. Die Wellenmuster kommen [bei mir] so zustande, dass an diesen Stellen sr viel größer ist als ul. Deshalb müssen mehr Kopieroperationen ausgeführt werden, was zu längeren Laufzeiten führt.
Hier mein Algo jetzt:
http://i44.tinypic.com/1zfs9d1.png
Da bei Mergesort hat Java wohl gerade einen Cache geleert oder gefüllt. Anders kann ich mir diese Ausreißer nicht erklären. Die treten immer wieder mal bei verschiedenen Algorithmen auf.
PS: Das mit dem s erhöhen habe ich auch.
-
- Beiträge: 225
- Registriert: Sa 25. Okt 2008, 12:48
Re: Algorithmen[Prog1]
Hat mir jemand einen Tipp wie ich s_r und u_l möglichst effizient vertauschen kann, wenn in u_l weniger Elemente als in s_r enthalten sind? Danke.