Schrift
Wiki:Tipp zum Debugging: use Data::Dumper; local $Data::Dumper::Useqq = 1; print Dumper \@var;
[thread]7585[/thread]

Sort VS Schwartz'sche sort ??? - Benchmark

Leser: 2


<< |< 1 2 3 >| >> 22 Einträge, 3 Seiten
Updecrator
 2006-01-03 11:05
#61449 #61449
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 )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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
#61450 #61450
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
#61451 #61451
User since
2003-08-04
7321 Artikel
ModeratorIn

user image
der regexp kostet geld
Updecrator
 2006-01-03 11:45
#61452 #61452
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
pq
 2006-01-03 11:48
#61453 #61453
User since
2003-08-04
12207 Artikel
Admin1
[Homepage]
user image
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
#61454 #61454
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
#61455 #61455
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

<!--EDIT|esskar|1136282532-->
steffenw
 2006-01-03 19:36
#61456 #61456
User since
2003-08-15
692 Artikel
BenutzerIn
[Homepage] [default_avatar]
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

<!--EDIT|steffenw|1136309848-->
$SIG{USER} = sub {love 'Perl' or die};
Strat
 2006-01-03 19:40
#61457 #61457
User since
2003-08-04
5246 Artikel
ModeratorIn
[Homepage] [default_avatar]
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
#61458 #61458
User since
2003-08-15
692 Artikel
BenutzerIn
[Homepage] [default_avatar]
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};
<< |< 1 2 3 >| >> 22 Einträge, 3 Seiten



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