[Tokyo.pm] JUS感想

Kazumasa Utashiro utashiro @ iij.ad.jp
1999年 9月 27日 (月) 11:03:06 CDT


From: harada goichi <goichi @ mb.kcom.ne.jp>
Subject: [Tokyo.pm] JUS感想
Date: Sun, 26 Sep 1999 23:46:15 +0900

> 次に、リファレンスを使った実例であるSchwartzian Transformについての
> 解説がありました。Schwartzian Transformとは、複雑な条件のsortを効率的に
> 実行するためのアルゴリズムです。

効率的でしょうか?

======================================================================
sub normal {
    my $listp = shift;
    my @length = map {length} @{$listp};
    @$listp[sort {$length[$a] <=> $length[$b]} 0 .. $#length];
}
sub st {
    my $listp = shift;
    map {$_->[0]} sort {$a->[1] <=> $b->[1]} map {[$_, length($_)]} @$listp;
}

@words = `head -5000 /usr/share/dict/words`;

use Benchmark;
timethese(10, {
	       'Normal'   => sub { normal(\@words) },
	       'Schwartz' => sub { st(\@words) },
	      }
	 );
======================================================================

というコードを実行すると、次のような結果が出ます。

======================================================================
Benchmark: timing 10 iterations of Normal, Schwartz...
    Normal:  2 wallclock secs ( 2.60 usr +  0.01 sys =  2.61 CPU)
  Schwartz:  7 wallclock secs ( 6.63 usr +  0.00 sys =  6.63 CPU)
======================================================================

では、プログラミングの効率が高くなるかというと、そうでもないと思います。
パズルとしては面白いんですが。

--utashiro


p.s. 上のコードの場合

sub shabby {
    my $listp = shift;
    my @list = sort {length($a) <=> length($b)} @$listp;
}

というのが一番速いんですけどね :-)。


p.p.s. 上の &shabby では @list に代入する必要はないのですが、結果を使
わないと sort を実行してくれなくて、ベンチマークになりません。



Tokyo-pm メーリングリストの案内