[Tokyo.pm] Re: [Tokyo.pm] ＪＵＳ感想

[IMAZU Hideyo]

At 99/9/30 01:38 +0900, Kazumasa Utashiro wrote:
> From: maeda ＠ src.ricoh.co.jp
> Subject: Re: [Tokyo.pm] ＪＵＳ感想
> Date: Wed, 29 Sep 1999 10:38:32 +0900
> 
> > advancedプログラミングの講義ではSchwartzian Transformが必ず出て
> > きますが、それはlisp的プログラミング、リファレンスによるデータ構
> > 造などを勉強する上でちょうど良い題材で、効率もそこそこで実用的と
> > いうことなのでしょう。
> 
> 遅い原因はデータ構造が若干複雑になることですから、比較条件の複雑さにか
> かわらず余計にかかる時間はほとんど変わらないはずです。

同感です。

ところで、私は歌代さんの意図を理解するのにちょっと時間がかかったので、一
応私なりに歌代さんの意図を言い換えてみます。歌代さんがおっしゃっているのは：

--ここから--
シュワルツ変換を単純にPerlで書いた

@sorted = map { $_->[0] }
          sort { $a->[1] cmp $b->[1] }
          map { [$_, &make_comparison_string($_)] } @unsorted;

は、歌代さんの書法

@cmpstr = map { &make_comparison_string($_) } @unsorted;
@sorted = @unsorted[ sort {$cmpstr[$a] cmp $cmpstr[$b]} 0..$#unsorted ];

より、効率は悪い。どちらも関数make_comparison_stringの実行回数は同じなの
で(並べ替える要素の数の回数)で、その意味で本質的効率は同じだが、シュワル
ツ変換のほうが、
・並べ替えるデータを map { [$_, &make_comparison_string($_)] } で変換して
・並べ替えて
・その結果からデータだけを map { $->[0] } で取り出す
というより多くのデータ操作を行っている分、実行時間は長くなるし、使用する
メモリーも多い。
--ここまで--

です。シュワルツ変換のキモは比較のための計算量を最低限にするといいうこと
ですから、歌代さんの書法はそのキモをPerlでより効率良く実装している思いま
す。また、より分かり易いとも思います。もちろん分かり易いと言うのはシュワ
ルツ変換と比較した場合の私の感触であって、初心者にとってわかりにくいこと
には変わりありませんが。

上記のシュワルツ変換の書法は Perl Cookbook でも紹介されていますから、歌代
さんの書法はその筆者に対して、「Perlではこう書くのが正しい」と指摘するに
値することだと思います。もう既になさってますか、歌代さん。歌代さんの書法
が紹介された今となっては上記のシュワルツ変換の書法を使う実用価値は何もな
いと思います。

--
今津 英世 (いまづ ひでよ)
モルガン・スタンレー証券 東京支店