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