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

[Kazumasa Utashiro]

From: Inaba Hiroto <inaba ＠ st.rim.or.jp>
Subject: わかりやすいソート (Re: [Tokyo.pm]  Re: 	[Tokyo.pm] ＪＵＳ感想)
Date: Thu, 07 Oct 1999 01:07:25 +0900

> 歌代さんが「tied array を使って lazy evaluation」というアイデアを書い
> てられましたが、それに似ている、Hashを使う以下のような方法を昔考えまし
> た。
> 
> my %cmpstr;
> @sorted = sort {
> 	    ($cmpstr{$a} ||= make_comparison_string($a)) cmp
> 	    ($cmpstr{$b} ||= make_comparison_string($b)) } @unsorted;
> 
> # このままだとmake_comparison_stringが0や""をかえすとまずい（余分に
> # 評価する）ですが、existsをつかってかけば避けられます
> 
> ソートする配列の要素が文字列でなくてはならないという制限がありますし、
> 効率は多分Schwartzian Transformよりもよくありませんし、冗長ですが、
> 自分としてはわかりやすいと思っているのですが、どうでしょうか？

いやいや、Jon Bentley 先生がもし Perl を使うとしたら出て来そうなコーディ
ングじゃないですか。||= は使わないかも知れませんが。

僕が出した例の『キモ』は、初期化の部分を変更するだけで効率を上げられる
(かもしれない) ということと、単に tie を使ってみたかったということです。
効率を考えれば、inline で書いた方がきっと速いですね。

> ソートする配列に同じ要素が多く含まれているなら、速いときもあるかも知れま
> せん。

なるほど、面白い視点です。『アルゴリズム』的に更に進んでますよね。

> # 考え方に慣れてしまえば、Schwartzian Transformもそんなに
> # トリッキーでもないと思うんですけど...

はい、NSPIXP はなかなか憶えられなくても、PCMCIA って普通に喋ってますか
ら。

--utashiro