[Tokyo.pm] Re: わかりやすいソート (Re: [Tokyo.pm] Re: [Tokyo.pm] ＪＵＳ感想)

[scozens ＠ pwj.co.jp]

前田さん：
    wrong:
     @keys1 = map { getkey1($_) } @unsorted;
     @keys2 = map { getkey2($_) } @unsorted;
    right:
     for (@unsorted) {
         push(@keys1, getkey1($_));
         push(@keys2, getkey2($_));
     }
理由はみなさんおわかりですね。

-------

いや、いや、ちょっと待って！ 対照実験ではありません！

mapよりforeachの方がたいてい速い; その上、信じがたいことだが、
理屈は至極だが、時々リストを二回繰り返す方が一回より速いです。
（速くない時、差が最小限です）

例えば：

----

bash-2.02$ perl testit.pl
Benchmark: timing 100 iterations of for_once, for_twice, hash, map_once,
map_twi
ce...
  for_once:  3 wallclock secs ( 3.44 usr +  0.02 sys =  3.46 CPU)
 for_twice:  3 wallclock secs ( 3.37 usr +  0.04 sys =  3.41 CPU)
      hash:  4 wallclock secs ( 3.92 usr +  0.00 sys =  3.92 CPU)
  map_once:  6 wallclock secs ( 5.38 usr +  0.00 sys =  5.38 CPU)
 map_twice:  4 wallclock secs ( 4.66 usr +  0.00 sys =  4.66 CPU)

------

これはもうすこしフェアな実験だと思います：

For 5000 elements...
Benchmark: timing 500 iterations of for_loop_once, for_loop_twice,
for_sm_once, for_sm_twice, hash, map_once, map_twice...
for_loop_once: 48 wallclock secs (48.64 usr +  0.00 sys = 48.64 CPU)
for_loop_twice: 52 wallclock secs (51.20 usr +  0.00 sys = 51.20 CPU)
for_sm_once: 47 wallclock secs (47.43 usr +  0.00 sys = 47.43 CPU)
for_sm_twice: 49 wallclock secs (49.28 usr +  0.00 sys = 49.28 CPU)
      hash: 48 wallclock secs (48.05 usr +  0.00 sys = 48.05 CPU)
  map_once: 182 wallclock secs (181.64 usr +  0.00 sys = 181.64 CPU)
 map_twice: 66 wallclock secs (65.96 usr +  0.00 sys = 65.96 CPU)

ついてながら、hashの方をstatement modifierのような形になると、
一番速いと思います。

use Benchmark;

open(TEST, "control.tex"); { undef $/; $_=<TEST>; } close TEST;
@unsorted=(split)[1..5000]; # Just some random words.

print "For ",scalar @unsorted," elements...\n";
timethese(500,
     {
          map_twice => sub {
              my (@keys1, ＠ keys2); # Make sure we've a clean slate.
              @keys1 = map { getkey1($_) } @unsorted;
              @keys2 = map { getkey2($_) } @unsorted;
          },
          map_once => sub {
               my (@keys1, ＠ keys2);
               map {push(@keys1, getkey1($_)),
                    push(@keys2,getkey2($_))
               } @unsorted;
          },
          for_sm_twice => sub { # sm == statement modifier
               my (@keys1, ＠ keys2);
               push @keys1, getkey1($_) for @unsorted;
               push @keys2, getkey2($_) for @unsorted;
          },
          for_loop_twice => sub {
               my (@keys1, ＠ keys2);
               for (@unsorted) { push @keys1, getkey1($_) };
               for (@unsorted) { push @keys2, getkey2($_) };
          },
          for_loop_once => sub {
               my (@keys1, ＠ keys2);
               foreach(@unsorted) {
                    push @keys1, getkey1($_);
                    push @keys2, getkey2($_);
               }
          },
          for_sm_once => sub {
               my (@keys1, ＠ keys2);
               (push(@keys1,getkey1($_)),
               push(@keys2,getkey2($_))) for @unsorted;
          },
          hash => sub { # Cute and fast.
               my %hash;
               my (@keys1, ＠ keys2);
               foreach(@unsorted) {
                    $hash[getkey1($_)]=getkey2($_);
               };

# Try "$hash[getkey1($_)]=getkey2($_) for @unsorted" for more fun

               @keys1=keys %hash; @keys2=values %hash;
          }
     }
);

# Just some dummy functions
sub getkey1 { return reverse shift() }
sub getkey2 { return shift()."foo" }

# Simon

--
Japanese And Perl Hacker.