In message <199910150248.LAA16166 / hoyogw.netlab.co.jp>
wakou / fsinet.or.jp writes:

> やり直してみると、わたなべさんのご心配通り、[]<=>[] が遅くなり、
> Schwartzian Transform が最も高速となりました。という事で、[]<=>[] より
> も見やすいとも思いますし、マニュアルの sort の所に Schwartzian
> Transform を載せ、これを推奨とするとか、あるいは以前 Hash の時に、わた
> なべさんが書かれたような Keysort のようなモジュールを用意という手もあ
> りますね。

ところで，`Scwartzian Transform' の本質というのは，

    あるデータセット S に対し，各要素とそれを処理する基準となるデータ
    との組からなるデータセット K*S を生成し，K*S の上で処理を行った後
    で目的のデータセット S' を得ること

で良いのでしょうか．

# 中途半端に厳密性を求めた記述 (^^;


たとえば sort を例にすると，整数値を表す文字列の配列

    ["10", "1", "2"]

から整数としての値と文字列の組の配列

    [[10, "10"], [1, "1"], [2, "2"]]

をつくり，これをキーである整数値でソートした結果 

    [[1, "1"], [2, "2"], [10, "10"]]

から数値順の文字列の配列

    ["1", "2", "10"]

を得る．

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


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

# sort 以外の有意義な利用例って，なにかあるかな?


たまに定義を確認しないと不安になるもので．よく変な理解をして後で困る (^^;


-- 
柳川和久 @ 東大阪市 . 大阪府                               October 15, 1999
「変なことを考えるのにも限界があると思わない?」
「なんで変なことを書く必要がある」「小説が現実に負けてどうするのよ !」