such mal nach Guttman-Rosler

Wahnsinn, was ich da alles gefunden habe:
http://www.sysarch.com/Perl/sort_paper.html (wie Sortieren)
http://cpan.uwinnipeg.ca/htdocs/Sort-Maker/Sort/Maker.pm.html (das Modul für alle Verfahren (hier mit Quelltext))
http://stemsystems.com/sort/slides/slides/index.html (wie's funktioniert)

ja, ja, das internet!

Hi Updecrator,

[quote=Updecrator,03.01.2006, 10:05]Eigentlich sollte Schwartz'sche Sort viel schneller als die normale Sortierung,[/quote]

wenn du die Schwarzsche Transformation sinnvoll verwendest, dann ist
sie das auch. Zum Beispiel lassen sich tabellenähnliche Zeilen damit
wunderbar sortieren ...



... weiteres Beispiel ... falls du ne Linuxbüchse hast :)



Greez,
opi

Was ich heute hier gelernt habe ist, daß die Guttman-Rosler-Variante auf den Perl-Callback beim sort vollständig verzichtet und damit im sort-Teil nur noch das nackte sort steht und somit auch nur reiner C-Code ausgeführt wird. :) Die Intelligenz ist somit auf die Vor- und Nachbereitungsphase verschoben, was bei der Schwarzschen nicht ist. :( Da ist der sort-Teil nur rmittelmäßig schnell.

map gibt es in 2 Varianten:
@a2 = map "irgendwas $_", @a1;
oder
@a2 = map {"irgendwas $_"} @a1;
Durch den {} Block wird jedes Mal der Garbage-Collector angeworfen, was bei der ersten nicht ist.\n\n

<!--EDIT|steffenw|1136329167-->

[quote=steffenw,03.01.2006, 18:36]Ich weiß nicht warum, aber ich sortiere in der Schwarzschen immer den Index 0 ($a->[0]) und nicht den Index 1 ($a->[1]). Ich weiß nicht, wie das in Perl genau ist, aber ich kenne Programmierspachen in denen Index 0 immer schneller war als die anderen Indizes (weil, Adresse des Arrays ist gleich der Adresse des Elements mit Index 0). Eigentlich ist es ja der Schwarschen egal, was nun Index 0 oder 1 ist.[/quote]
Ich mache es genauso, aber das wird wohl eher Aberglaube sein :-)

[quote=steffenw,03.01.2006, 23:53]
map gibt es in 2 Varianten:
@a2 = map "irgendwas $_", @a1;
oder
@a2 = map {"irgendwas $_"} @a1;
Durch den {} Block wird jedes Mal der Garbage-Collector angeworfen, was bei der ersten nicht ist.[/quote]
Du meinst wohl: bei der {...}-Notation wird mit Scopes gearbeitet, wobei durch das Reference-Counting Variablen zerstört werden können (eine klassische GC hat Perl5 ja nicht).

Und tatsächlich:


Hiermit bekomme ich mit der "code"-Variante 1% langsamere Ergebnisse. Naja, damit kann ich leben, ich finde die {...}-Variante einfach schöner zu lesen.

Hallo, zusammen,

vielen Dank fuer die Infos!
so lernt man, :)

Ueber die Sortierung mit Index [0] oder [1],
habe ich immer [1] gewaehlt, und es gibt doch einen kleinen Unterschied bei der Laufzeit (10000 rand.s, 100 iterations):

Quote

10000 numbers created !
Benchmark: timing 100 iterations of Schwartz sort mit Index [1] ...
Schwartz sort mit Index [1] : 15 wallclock secs (13.09 usr + 0.14 sys = 13.23 CPU) @ 7.56/s (n=100)
Benchmark: timing 100 iterations of Schwartz sort mit Index [0] ...
Schwartz sort mit Index [0] : 15 wallclock secs (14.03 usr + 0.12 sys = 14.15 CPU) @ 7.07/s (n=100)
Rate Schwartz sort mit Index [0] Schwartz sort mit Index [1]
Schwartz sort mit Index [0] 7.07/s -- -7%
Schwartz sort mit Index [1] 7.64/s 8% --

Viel Gruss

Arrayzugriff ist normalerweise:
integer = array[index]
integer = Inhalt(Speicheradresse(array) + Strukturlänge_hier(Integer) * index)

nur bei Index 0 kann optimiert werden:
integer = Inhalt(Speciheradresse(array))

Ich habe vor gut 20 Jahren, wo man noch wenig Speicher hatte, optimieren müssen, damit das Projekt überhaupt realisierbar war. Und da hat man einfach reassembliert und sich angeschaut, was letztendlich beim Compilieren herauskommt und so optimiert. Es ist interessant und zum Teil auch heute noch aktuell, weil sich die Algorithmen teilweise nicht geändert haben. Dabei sah man jedoch, daß Arrayzugriffe viel Code produzieren, weil sie eben ausmultipliziert werden müssen. Das Arbeiten mit mehrdimensionalen Arrays ist dann völliger Wahnsinn. Zum Glück ist letztes in Perl gar nicht erst implementiert worden. Zeiger waren damals die Lösung, heute sind es elegante Referenzen. Somit ist heute for (i = 0; $i < ...; ...) immer noch zweite Wahl, wenn man for (@array) nehmen kann.

[quote=ptk,04.01.2006, 00:48]Hiermit bekomme ich mit der "code"-Variante 1% langsamere Ergebnisse. Naja, damit kann ich leben, ich finde die {...}-Variante einfach schöner zu lesen.[/quote]
Ich nehme beide Varianten, weil ich festgestellt habe, daß Perl die 2 Varianten nicht nur zum Auswählen anbietet, sondern jede ihnen Sinn hat. In dem Beispiel, @ptk, ist die Variante ohne {} einfacher lesbar, Zeichenmüll entfällt einfach. Aber wenn es mehr wird, bleibt sowieso meist nichts anderes übrig, als {} zu nehmen, sonst muß man Kopfstände machen, die dann die Lesbarkeit nicht erhöhen, sondern eher das Gegenteil bewirken.