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