わたなべです.

YANAGAWA Kazuhisa <kjana / os.xaxon.ne.jp> writes:

:ところで,`Scwartzian Transform' の本質というのは,
:
:    あるデータセット S に対し,各要素とそれを処理する基準となるデータ
:    との組からなるデータセット K*S を生成し,K*S の上で処理を行った後
:    で目的のデータセット S' を得ること
:
:で良いのでしょうか.

perl の map, sort, map が本質だから, そういうことになります.

:# ruby だと `["10", "1", "2"].filter {|e| [e.to_i, e]}.sort.filter {|e| e[1]} 
:# ですんでしまう.

この例の場合 perl だと
  map {$_->[0]} sort {$a->[1] <=> $b->[1]} map {[$_, int($_)]} ("10", "1", "2")
って全然意味ないか. もっと複雑じゃないと.

:利点はキーデータ生成の計算量が O(N) になること.たとえば sort の例の場
:合,比較毎にキーを作っていると,最良でも計算量は O(NlogN) になる.

結局 qsort の比較回数になるわけですね.
これで稼いだ分と余分な配列等を作ったオーバーヘッドとの勝負.
あと当然メモリも喰いますね.

-- 
わたなべひろふみ