Re: Perls Listen

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

-- 
Um die Liste abzubestellen, schicken Sie eine Mail an:
    [email protected]
Um eine Liste aller verfÃŒgbaren Kommandos zu bekommen, schicken
Sie eine Mail an: [email protected]