Hallo, Weiß hier jemand zufälligerweise, ob man in Perl durch irgendein Modul die Listen durch echte Arrays mit ein konstanten Zugriffszeit auf ein beliebiges Element ersetzen kann? Das ist für meinen Fall hier jetzt nicht wichtig, aber O(n) wäre schon ein bisschen schöner als O(n^2). Ferdinand
Hallo, Am Tue, 28 Jun 2005, Ferdinand Ihringer schrieb:
Weiß hier jemand zufälligerweise, ob man in Perl durch irgendein Modul die Listen durch echte Arrays mit ein konstanten Zugriffszeit auf ein beliebiges Element ersetzen kann? Das ist für meinen Fall hier jetzt nicht wichtig, aber O(n) wäre schon ein bisschen schöner als O(n^2).
$ cat perlarray.pl #!/usr/bin/perl -w use Benchmark qw(timethese); open(DN, ">/dev/null") or die "$!\n"; foreach my $l (@ARGV) { print "using array of $l elements\n"; timethese(100, { "loop" => sub { my @arr; for($i=0; $i < $l; ++$i) { $arr[$i]=$i; }; for($i=0; $i < $#arr; ++$i) { print DN $arr[$i/2]; }; } }); } close(DN); $ perl perlarray.pl 1000 10000 100000 using array of 1000 elements Benchmark: timing 100 iterations of loop... loop: 1 wallclock secs ( 1.19 usr + 0.00 sys = 1.19 CPU) @ 84.03/s (n=100) using array of 10000 elements Benchmark: timing 100 iterations of loop... loop: 13 wallclock secs (12.20 usr + 0.00 sys = 12.20 CPU) @ 8.20/s (n=100) using array of 100000 elements Benchmark: timing 100 iterations of loop... loop: 127 wallclock secs (126.56 usr + 0.03 sys = 126.59 CPU) @ 0.79/s (n=100) Fuer mich sieht das verdammt nach O(n) aus. -dnh -- Q: What's the difference between a Used Car SalesPerson and a Computer SalesPerson? A: The Used Car SalesPerson KNOWS when they're lying.
Hallo, Am Dienstag 28 Juni 2005 21:30 schrieb David Haller:
Hallo,
Am Tue, 28 Jun 2005, Ferdinand Ihringer schrieb:
Weiß hier jemand zufälligerweise, ob man in Perl durch irgendein Modul die Listen durch echte Arrays mit ein konstanten Zugriffszeit auf ein beliebiges Element ersetzen kann? Das ist für meinen Fall hier jetzt nicht wichtig, aber O(n) wäre schon ein bisschen schöner als O(n^2).
$ perl perlarray.pl 1000 10000 100000 using array of 1000 elements Benchmark: timing 100 iterations of loop... loop: 1 wallclock secs ( 1.19 usr + 0.00 sys = 1.19 CPU) @ 84.03/s (n=100) using array of 10000 elements Benchmark: timing 100 iterations of loop... loop: 13 wallclock secs (12.20 usr + 0.00 sys = 12.20 CPU) @ 8.20/s (n=100) using array of 100000 elements Benchmark: timing 100 iterations of loop... loop: 127 wallclock secs (126.56 usr + 0.03 sys = 126.59 CPU) @ 0.79/s (n=100)
Fuer mich sieht das verdammt nach O(n) aus.
Stimmt. Ich habe mich verzählt/verrechnet/wiemandasauchnennenwill und schrieb die Schuld Perl zu, weil ich dachte, es wären Listen. Ich wasauchimmerte nochmal nach und kam auf n^2. :-| Dafür warf sich für mich jetzt eine andere Frage auf: #!/usr/bin/perl -w use Benchmark qw(timethese); open(DN, ">/dev/null") or die "$!\n"; foreach my $l (@ARGV) { print "using array of $l elements\n"; my @arr; $#arr = $l; $_ = 0 foreach(@arr); $m = $#arr; timethese(0, { "code" => sub { print DN $arr[$m]; } }); $m = int($#arr/2); timethese(0, { "code" => sub { print DN $arr[$m]; } }); my $m = 0; timethese(0, { "code" => sub { print DN $arr[0]; } }); } close(DN); $ perl perlarrays.pl 100 100000 using array of 100 elements Benchmark: running code for at least 3 CPU seconds... code: 3 wallclock secs ( 3.59 usr + 0.00 sys = 3.59 CPU) @ 3773679.67/s (n=13547510) Benchmark: running code for at least 3 CPU seconds... code: 5 wallclock secs ( 3.05 usr + -0.01 sys = 3.04 CPU) @ 4567515.13/s (n=13885246) Benchmark: running code for at least 3 CPU seconds... code: 3 wallclock secs ( 3.02 usr + 0.00 sys = 3.02 CPU) @ 5337027.48/s (n=16117823) using array of 100000 elements Benchmark: running code for at least 3 CPU seconds... code: 4 wallclock secs ( 3.12 usr + 0.00 sys = 3.12 CPU) @ 3911077.24/s (n=12202561) Benchmark: running code for at least 3 CPU seconds... code: 6 wallclock secs ( 3.14 usr + 0.00 sys = 3.14 CPU) @ 4314492.68/s (n=13547507) Benchmark: running code for at least 3 CPU seconds... code: 3 wallclock secs ( 3.42 usr + 0.01 sys = 3.43 CPU) @ 4596030.32/s (n=15764384) Warum variiert hier die Zugriffszeit so stark? Wo ist mein Messfehler? Ferdinand
Hallo, Am Wed, 29 Jun 2005, Ferdinand Ihringer schrieb: [..]
Stimmt. Ich habe mich verzählt/verrechnet/wiemandasauchnennenwill und schrieb die Schuld Perl zu, weil ich dachte, es wären Listen. Ich wasauchimmerte nochmal nach und kam auf n^2. :-|
Dafür warf sich für mich jetzt eine andere Frage auf: #!/usr/bin/perl -w use Benchmark qw(timethese); open(DN, ">/dev/null") or die "$!\n"; foreach my $l (@ARGV) { print "using array of $l elements\n";
my @arr; $#arr = $l; $_ = 0 foreach(@arr);
$m = $#arr; timethese(0, { "code" => sub { print DN $arr[$m]; } }); $m = int($#arr/2); timethese(0, { "code" => sub { print DN $arr[$m]; } }); my $m = 0; timethese(0, { "code" => sub { print DN $arr[0]; } }); } close(DN);
$ perl perlarrays.pl 100 100000 using array of 100 elements Benchmark: running code for at least 3 CPU seconds... code: 3 wallclock secs ( 3.59 usr + 0.00 sys = 3.59 CPU) @ 3773679.67/s (n=13547510) Benchmark: running code for at least 3 CPU seconds... code: 5 wallclock secs ( 3.05 usr + -0.01 sys = 3.04 CPU) @ 4567515.13/s (n=13885246) Benchmark: running code for at least 3 CPU seconds... code: 3 wallclock secs ( 3.02 usr + 0.00 sys = 3.02 CPU) @ 5337027.48/s (n=16117823) using array of 100000 elements Benchmark: running code for at least 3 CPU seconds... code: 4 wallclock secs ( 3.12 usr + 0.00 sys = 3.12 CPU) @ 3911077.24/s (n=12202561) Benchmark: running code for at least 3 CPU seconds... code: 6 wallclock secs ( 3.14 usr + 0.00 sys = 3.14 CPU) @ 4314492.68/s (n=13547507) Benchmark: running code for at least 3 CPU seconds... code: 3 wallclock secs ( 3.42 usr + 0.01 sys = 3.43 CPU) @ 4596030.32/s (n=15764384)
Warum variiert hier die Zugriffszeit so stark? Wo ist mein Messfehler?
Du misst hier praktisch nicht den Arrayzugriff sondern eher den Funktionsaufruf und das "print". Du siehst ja selbst, dass die Ausfuehrungszeit praktisch nicht von der Groesse des Arrays abhaengig ist. BTW, besser als das print waere wohl: $arr[$m]++; oder sowas, auch bei meinem code. $ cat perlarray.pl #!/usr/bin/perl -w use Benchmark qw(timethese); foreach my $l (@ARGV) { print "using array of $l elements\n"; my @arr; for($i=0; $i < $l; ++$i) { $arr[$i]=$i; }; timethese(0, { "loop" => sub { for($i=0; $i < $#arr; ++$i) { $arr[$#arr/2]++; }; }, "zugriff" => sub { $arr[$#arr/2]++; } }); } $ perl perlarray.pl 100 1000 10000 100000 using array of 100 elements Benchmark: running loop, zugriff for at least 3 CPU seconds... loop: 3 wallclock secs ( 3.14 usr + 0.00 sys = 3.14 CPU) @ 2103.50/s (n=6605) zugriff: 2 wallclock secs ( 3.01 usr + 0.00 sys = 3.01 CPU) @ 270277.41/s (n=813535) using array of 1000 elements Benchmark: running loop, zugriff for at least 3 CPU seconds... loop: 3 wallclock secs ( 3.23 usr + 0.00 sys = 3.23 CPU) @ 210.53/s (n=680) zugriff: 3 wallclock secs ( 3.03 usr + 0.00 sys = 3.03 CPU) @ 289927.06/s (n=878479) using array of 10000 elements Benchmark: running loop, zugriff for at least 3 CPU seconds... loop: 4 wallclock secs ( 3.15 usr + 0.00 sys = 3.15 CPU) @ 20.95/s (n=66) zugriff: 3 wallclock secs ( 3.05 usr + 0.00 sys = 3.05 CPU) @ 285301.97/s (n=870171) using array of 100000 elements Benchmark: running loop, zugriff for at least 3 CPU seconds... loop: 4 wallclock secs ( 3.34 usr + 0.00 sys = 3.34 CPU) @ 2.10/s (n=7) zugriff: 3 wallclock secs ( 3.01 usr + 0.00 sys = 3.01 CPU) @ 281302.33/s (n=846720) Man sieht sehr schoen, dass "loop" mit O(n) laeuft, d.h. linear von der Groesse 'n' des Arrays abhaengt. Das Produkt aus "loop" pro s mal Groesse 'n' des Arrays ist bei allen Messungen ungefaehr 210000. "zugriff" laeuft mit O(1) (jew. 280k +- 10k mal pro Sekunde, d.h. im Rahmen der Messungenauigkeit mit konstanter Laufzeit (modulo geringe andere Einfluesse wie das $#arr / 2). HTH, -dnh -- "Wenn das Wörtchen 'wenn' nicht wär' , wär' die Platte jetzt nicht leer." -- ratti in suse-linux
Hallo, Am Mittwoch 29 Juni 2005 18:53 schrieb David Haller:
Am Wed, 29 Jun 2005, Ferdinand Ihringer schrieb: [..]
Stimmt. Ich habe mich verzählt/verrechnet/wiemandasauchnennenwill und schrieb die Schuld Perl zu, weil ich dachte, es wären Listen. Ich wasauchimmerte nochmal nach und kam auf n^2. :-|
Dafür warf sich für mich jetzt eine andere Frage auf: #!/usr/bin/perl -w use Benchmark qw(timethese); open(DN, ">/dev/null") or die "$!\n"; foreach my $l (@ARGV) { print "using array of $l elements\n";
my @arr; $#arr = $l; $_ = 0 foreach(@arr);
$m = $#arr; timethese(0, { "code" => sub { print DN $arr[$m]; } }); $m = int($#arr/2); timethese(0, { "code" => sub { print DN $arr[$m]; } }); my $m = 0; timethese(0, { "code" => sub { print DN $arr[0]; } }); } close(DN);
$ perl perlarrays.pl 100 100000 using array of 100 elements Benchmark: running code for at least 3 CPU seconds... code: 3 wallclock secs ( 3.59 usr + 0.00 sys = 3.59 CPU) @ 3773679.67/s (n=13547510) Benchmark: running code for at least 3 CPU seconds... code: 5 wallclock secs ( 3.05 usr + -0.01 sys = 3.04 CPU) @ 4567515.13/s (n=13885246) Benchmark: running code for at least 3 CPU seconds... code: 3 wallclock secs ( 3.02 usr + 0.00 sys = 3.02 CPU) @ 5337027.48/s (n=16117823) using array of 100000 elements Benchmark: running code for at least 3 CPU seconds... code: 4 wallclock secs ( 3.12 usr + 0.00 sys = 3.12 CPU) @ 3911077.24/s (n=12202561) Benchmark: running code for at least 3 CPU seconds... code: 6 wallclock secs ( 3.14 usr + 0.00 sys = 3.14 CPU) @ 4314492.68/s (n=13547507) Benchmark: running code for at least 3 CPU seconds... code: 3 wallclock secs ( 3.42 usr + 0.01 sys = 3.43 CPU) @ 4596030.32/s (n=15764384)
Warum variiert hier die Zugriffszeit so stark? Wo ist mein Messfehler?
Du misst hier praktisch nicht den Arrayzugriff sondern eher den Funktionsaufruf und das "print". Du siehst ja selbst, dass die Ausfuehrungszeit praktisch nicht von der Groesse des Arrays abhaengig ist.
print gibt aber in jedem Fall genauso viel aus. Immer eine 0. Sollte dann der Funktionsaufruf nicht immer gleich schnell sein? [ein anderer Benchmark]
Man sieht sehr schoen, dass "loop" mit O(n) laeuft, d.h. linear von der Groesse 'n' des Arrays abhaengt. Das Produkt aus "loop" pro s mal Groesse 'n' des Arrays ist bei allen Messungen ungefaehr 210000.
"zugriff" laeuft mit O(1) (jew. 280k +- 10k mal pro Sekunde, d.h. im Rahmen der Messungenauigkeit mit konstanter Laufzeit (modulo geringe andere Einfluesse wie das $#arr / 2).
Das ist jetzt schon klar. Wie gesagt, vergaß ich ein n beim Rechnen. Ferdinand
participants (2)
-
David Haller -
Ferdinand Ihringer