シュワルツ変換とRuby

ソートのときに比較関数が何らかの計算を含む場合、計算に重複が出て処理性能が落ちる。これを避けるために、あらかじめ計算結果と一緒に連想配列のような入れ物を別途用意して並べ直すのが一般的なようだ。1994年にPerlハッカーのランダル・シュワルツがPerlイディオムとして書いたことから広く「シュワルツ変換」と呼ばれている、とWikipediaにある。Lispではもともとasoccを使ったりして同様のことをやっていたので、Perlのイディオムに付いた名前が一般化したということらしい。

ちょっと検索すると、いろんな言語でのシュワルツ変換が出てくるけど、Ruby では何と組み込みだった。Enumerable#sortには、以下の解説が。

As of Ruby 1.8, the method Enumerable#sort_by implements a
built-in Schwartzian Transform, useful when key computation or
comparison is expensive..

sort_byがシュワルツ変換入りのソート。ただし、いつも使うべきというわけじゃない。enum#sort_by の説明を見ると、sort_byでかえって遅くなる例と高速になる例が出ている。現在のRubyの実装では、sort_byに単純なブロックを渡した場合、ソート対象として一時的に作るタプル（ってRubyじゃ聞かない用語けど、immutableなarrayってことか？）を生成するコストのほうが高くなって、実は遅くなってしまう。でも、ファイルをタイムスタンプ順に並べ替えるようなときにはファイルI/Oを抑えることになるので、高速になるという。なるほど。

array.cには、Array#sott!の定義として、次のような箇所がある。

1756 rb_ary_sort_bang(VALUE ary)
1757 {
1758     rb_ary_modify(ary);
1759     assert(!ARY_SHARED_P(ary));
1760     if (RARRAY_LEN(ary) > 1) {
1761         VALUE tmp = ary_make_substitution(ary); /* only ary refers tmp */
1762         struct ary_sort_data data;
1763 
1764         RBASIC(tmp)->klass = 0;
1765         data.ary = tmp;
1766         data.opt_methods = 0;
1767         data.opt_inited = 0;
1768         ruby_qsort(RARRAY_PTR(tmp), RARRAY_LEN(tmp), sizeof(VALUE),
1769                    rb_block_given_p()?sort_1:sort_2, &data);

1761行目でtmpにオリジナルのaryをコピーしたArrayオブジェクトを作り、これを並べ替えている。このとき、ary_sort_dataという構造体を使ってるけど、ドキュメントにあるタプルというのはこれのことじゃないかという気がする。

1670 struct ary_sort_data {
1671     VALUE ary;
1672     int opt_methods;
1673     int opt_inited;
1674 };

んー、あれ。単にintが2つあるだけか、、、。しかも単純にオプションスイッチ？ 分からん。

ともあれ、Rubyでは、シュワルツ変換という言葉や概念を知らなくても、sortで凝ったブロックを渡すときにはsort_byを使うと覚えておけば、それほどひどいことにならない。やっぱりRubyって素敵だなと思った。