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