comparefn

.js .st

Array.prototype.sort が受け取る比較関数は

comparefn が undefined でないならば、それは 2 個の引数 x と y を受け付け、 x < y ならば負の値、 x = y ならば 0、 x > y ならば正の値を返す関数であるべきである。

http://www2u.biglobe.ne.jp/~oz-07ams/prog/ecma262r3/15-4_Array_Objects.html#section-15.4.4.11

という仕様で，これを真面目に書くと

// sorting by 'str' property
arr.sort(function(x, y){ return x.str > y.str ? -1 : x.str < y.str ? 1 : 0 }

のようになりえらく辛気臭い。
本来ソートするために必要な情報はその並びが正しいか否かのみであるはずで，実際 Smalltalk ではこう書く。

arr asSortedCollection sortBlock: [:x :y| x str <= y str ]

ブロック内の記述が並べ方そのものになっていて直感的である。
JavaScript でも同様に書けないだろうか？

実験

記述を簡潔化するため，返値の種類を減らしてみる。

var fs = ['+!(x<=y) ', '-(x<=y)  ', '.5-(x<=y)', '(x>y)-(x<y)'], f;
//for(var a = [], i = 99; i--;) a[i] = Math.random();
for(var a = [], i = 1e4; i--;) a[i] = Math.random() > .1;
var result = '', sorted = a.slice().sort()+'';
while((f = fs.shift())) result += f +' => '+
  (a.slice().sort(Function('x,y', 'return'+ f))+''===sorted?'OK':'NG')+'\n';
(typeof alert !== 'undefined' ? alert : print)(result);

上記を Rhino1.7 で実行すると以下の結果を得る。

+!(x<=y)  => OK
-(x<=y)   => NG
.5-(x<=y) => OK
(x>y)-(x<y) => OK

上から順に「0 or 1」「-1 or 0」「-.5 or .5」「-1, 0 or 1 (control)」を返してソートできるかどうか調べている。Rhino では負の値を使わない(正かそれ以外かで判定している)ことが伺える。
同じものを主要ブラウザで走らせた結果を示す。

codeFx3IE7Op9Sf3GC1
+!(x<=y) OKNGNGNGNG
-(x<=y) NGNGNGNGNG
.5-(x<=y)OKOKTTLSOFSOF

三つ目の形式で安定のようだ。無論四つ目は全て OK なので省略した。
Op9/Sf3/GC1 では時間が掛かり過ぎるか又はスタックオーバーフローし，まともにソートできない。

結論

Rhino/Firefox3/IE7 では sort に渡す比較関数に下記のより簡潔かつ直感的な形式が使用できる。

function comparefn(x, y){ return .5 - (x <= y) }
  • 「x <= y」の部分には「正しく並んでいるかどうかを示す真偽値」を返す式を記述。
  • Mozilla 系に限り「return !(x <= y)」と書いてもよい。
    仕様では Number 型を返すことになっているが，1|0 の代わりに true|false を返しても問題ない。
09-02-12

テストコード及び実験結果と結論の修正。