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

[Inaba Hiroto]

稲葉です。ここでははじめましてです。

IMAZU Hideyo wrote:

> シュワルツ変換を単純に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 ];
> 
> より、効率は悪い。...
	：
> 歌代さんの書法は...
	：
> ...また、より分かり易いとも思います。もちろん分かり易いと言うのはシュワ
> ルツ変換と比較した場合の私の感触であって、初心者にとってわかりにくいこと
> には変わりありませんが。

歌代さんが「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よりもよくありませんし、冗長ですが、
自分としてはわかりやすいと思っているのですが、どうでしょうか？

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

comp.lang.perl(.misc)だったかp5pだかで同じアイデアを見たような気がして、
後から探したのですが、見つける事ができませんでした。

# 考え方に慣れてしまえば、Schwartzian Transformもそんなに
# トリッキーでもないと思うんですけど...
--
			稲葉 浩人  <inaba ＠ st.rim.or.jp>