Sort VS Schwartz'sche sort ??? - Benchmark (Allgemeines zu Perl)

[thread]7585[/thread]

Sort VS Schwartz'sche sort ??? - Benchmark

Leser: 2

Updecrator

2006-01-03 11:05

User since
2005-11-16
17 Artikel
BenutzerIn
[default_avatar]

hallo, zusammen,

Eigentlich sollte Schwartz'sche Sort viel schneller als die normale Sortierung,
aber welchen Fehler habe ich bei der 'Benchmark' gemacht, sodass das Ergebnis umgekehrt ist?

Code: (dl )

use Benchmark;

my @numbers;

for (1..10000) {
    my $random = int( rand(9000)) + 5;
    push @numbers, $random;
}

print scalar @numbers, " numbers created !\n";

my $iterations = 100; 

timethese($iterations, {
  "Schwartz" => sub {
        my @sorted = map { $_->[0] }
        sort { $b->[1] <=> $a->[1] }
        map { my $num = $_; $num =~ /\d+/; [ $_, $num ]; } @numbers } 
        
   });

timethese($iterations, {
  "Normal sort" => sub {
        my @sorted = sort {$b <=> $a} @numbers;
    }
});

exit;

Nach der Ausfuehrung habe ich:

Quote
10000 numbers created !
Benchmark: timing 100 iterations of Schwartz...
Schwartz: 17 wallclock secs (13.40 usr + 0.18 sys = 13.58 CPU) @ 7.36/s (n=100)
Benchmark: timing 100 iterations of Normal sort...
Normal sort: 2 wallclock secs ( 1.50 usr + 0.04 sys = 1.54 CPU) @ 64.94/s (n=100)

Vielen Dank im Voraus!

coax

2006-01-03 11:37

User since
2003-08-11
457 Artikel
BenutzerIn
[default_avatar]

Du verwendest bei der Schwartzian-Transform-Sortierung 2 map-Anweisungen, ein Regexp, mehrere Dereferenzierungen, Variablendeklariationen und die Erzeugung eines anonymen Arrays, weshalb denkst du sollte dies schneller als ein simples sort { $a <=> $b } sein.
Schon auf den ersten Blick erkennt man dass dies nicht schneller sein kann, da zumal dieses simple sort (mit Dereferenzierung) schon in den Schwartzian-T-Sort vorkommt ?

,,Das perlt aber heute wieder...'' -- Dittsche

esskar

2006-01-03 11:39

User since
2003-08-04
7321 Artikel
ModeratorIn

user image

der regexp kostet geld

Updecrator

2006-01-03 11:45

User since
2005-11-16
17 Artikel
BenutzerIn
[default_avatar]

Hi, danke fuer die Hinweise !

d.h. ich habe einen Denkfehler gemacht.
Schwatz-Sort kann nicht immer schneller als das normale Sort sein.

Das "sort" ist tatsaechlich fuer sort {$a cmp $b} oder sort {$a <=> $b} am schnellsten.

Viel Gruss

2006-01-03 11:48

User since
2003-08-04
12208 Artikel
Admin1

vielleicht hast du den sinn der ST nicht verstanden.
wenn du nach $a <=> $b sortieren willst, warum benutzt du dann eine ST?
schneller kann es doch nicht gehen als zwei zahlen zu vergleichen.
stattdessen machst du in der ST etwas komisches:
map { my $num = $_; $num =~ /\d+/; [ $_, $num ]; } @numbers
du weist $_ der überflüssigen variable $num zu, darauf führst du einen match aus,
machts aber nix mit dem ergebnis und mappst das ganze auf [$_, $_] (sinngemäß).
dann schließlich sortierst du:
sort { $b->[1] <=> $a->[1] }
allein das ist natürlich schon etwas langsamer als $a <=> $b, weil auf array-
referenzen zugegriffen wird.

also, nicht äpfel mit birnen vergleichen. die ST ist da schneller, wo in der sort-
routine aufwändige sachen gemacht werden.

Always code as if the guy who ends up maintaining your code will be a violent psychopath who knows where you live. -- Damian Conway in "Perl Best Practices"
lesen: Wiki:

Wie frage ich & perlintro Wiki:

brian's Leitfaden für jedes Perl-Problem

Updecrator

2006-01-03 11:58

User since
2005-11-16
17 Artikel
BenutzerIn
[default_avatar]

hi, pq,

du hast recht, der Reg. macht's noch langsamer,

> map { my $num = $_; $num =~ /\d+/; [ $_, $num ]; } @numbers

;), vorher gibt es in @numbers auch andere Elemente, strings, chars, digits, ...

> die ST ist da schneller, wo in der sort-routine aufwändige sachen gemacht werden.

Ja, jetzt habe ich verstanden, danke schoen !

esskar

2006-01-03 12:00

User since
2003-08-04
7321 Artikel
ModeratorIn

user image

gehen wir doch mal durch, und versuchen rauszufinden was du da machst.

Code: (dl )

my $num = $_; $num =~ /\d+/; [ $_, $num ];

Du weißt $num dem Wert von $_; $_ ist eine Zahl. $num ist also auch eine Zahl. Mit dem Regexp prüfst du, ob $num eine Reihe von Zahlen enthält - änderst aber $num nicht. dann erzeugst du ein anonymes Array, wobei die Werte auf Index 0 und 1 identisch sind.

Code: (dl )

map { my $num = $_; $num =~ /\d+/; [ $_, $num ]; } @numbers

du baust ein Array aus Array-Referenzen. Dieses neue Array hat 1000 Einträge.

Code: (dl )

sort { $b->[1] <=> $a->[1] }

hier sortierst du die 1000 Einträge. da Index 0 und 1 identisch sind hättest du auch sort { $b->[0] <=> $a->[0] } schreiben können. genauer betrachtet ist dies schon das selbe wie dein normales sort my @sorted = sort {$b <=> $a} @numbers;

Code: (dl )

my @sorted = map { $_->[0] }

jetzt iterierst du nochmal über die 1000 Einträge und schreibst das erste elemente aus diesen anonymen referenzen in dein neues array - hättest auch my @sorted = map { $_->[1] } schreiben können :)

man sieht also, der erste algorithmus ist richtig sinnfrei! :p

PS: Kam etwas zu spät, diese Aufführung.\n\n

steffenw

2006-01-03 19:36

User since
2003-08-15
692 Artikel
BenutzerIn

Regex ohne Anker ist schon mal langsamer als eine mit

Code: (dl )

1
2

/\d+/ # ohne
/^\d+$/ # mit

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.\n\n

$SIG{USER} = sub {love 'Perl' or die};

Strat

2006-01-03 19:40

User since
2003-08-04
5246 Artikel
ModeratorIn

ST ist (genauso wie das Orc'sche Maneuvre) nur schneller, wenn bei einem normalen Sort bei jedem vergleichskriterium eine laengere aktion ausgefuehrt werden muesste, z.B.

Code: (dl )

@filesSorted = sort { -s $a <=> -s $b } @files

das -s wird fuer jeden Vergleich zweimal ausgefuehrt. Wenn man da groessere @files hat, macht es meist sinn, das -s pro Datei nur einmal auszufuehren, und das vorweg (ST), oder beim ersten vergleich (OM). Bei komplexeren Datenstrukturen kann es schneller sein oder auch nicht, die berechnung fuer die vergleichsbedingung zu cachen (meistens duerfte es aber schneller sein)
Interessant ist in manchen Faellen auch die Guttman-Roessler-Transform, die auf das zweidimensionale Array verzichtet.

perl -le "s::*erlco'unaty.'.dk':e,y;*kn:ai;penmic;;print"
http://www.fabiani.net/

steffenw

2006-01-03 19:53

User since
2003-08-15
692 Artikel
BenutzerIn

Hallo @Strat, die Guttman-Roessler-Transform steht weder in Deiner Seite http://www.fabiani.net/perl/basics/sort.shtml, noch konnte ich etwas darüber beim google finden. Laß uns bitte mal nicht dumm sterben.

$SIG{USER} = sub {love 'Perl' or die};

View all threads created 2006-01-03 11:05.