なるほど。Schwartzian Transformの意外な利用法だなあ。

snippets from shinichitomita’s journal - JavaScriptの配列をsort関数でシャッフルする
Array.prototype.shuffle = function() {
   return this.map(function(a){ return { weight: Math.random(), value: a } })
              .sort(function(a, b){ return a.weight - b.weight })
              .map(function(a){ return a.value });
}

でも、実践ではどうだろう。調べてみた。

ここでは、要素数10000をシャッフルする時間を計測している。

Fisher-Yates

まずは、Fisher-Yates法。コードは最速インターフェース研究会 :: 実践JavaScriptで配列をシャッフルする方法リファクタリングほぼそのまま。

MacBook Pro上のSafariでもFirefox 1.5でも、0.1秒とかからない。

Array.prototype.shuffle_fy = function() {
    var i = this.length;
    while(i){
        var j = Math.floor(Math.random()*i);
        var t = this[--i];
        this[i] = this[j];
        this[j] = t;
    }
    return this;
}
Start seconds.

Schwartzian Transform (Original)

次に、snippets from shinichitomita’s journal - JavaScriptの配列をsort関数でシャッフルするそのまま。本来のSchwartzian Transformでは連想配列ではなく配列を使うのだけど、こちらの方がわかりやすいといえばわかりやすい。

Safariでは2秒弱ほどかかった。

Array.prototype.shuffle_sto = function() {
   return this.map(function(a){ return { weight: Math.random(), value: a } })
              .sort(function(a, b){ return a.weight - b.weight })
              .map(function(a){ return a.value });
}

なお、Array.mapはSafariにも実装されていなかったので、以下のようにしてある。

if (! Array.prototype.map ){
  Array.prototype.map = function(f){
    var a = [];
    for(var i = 0; i < this.length; i++){
      a[i] = f(this[i]);
    }
    return a;
  }
}
Start seconds.

Schwartzian Transform (via Array)

そしてこちらが素直なSchwartzian Transform。

Safariでは倍近い速度が出るのだけど、Firefoxでは高速化は誤差の範囲だった。いずれにせよ1秒以上かかる。

Array.prototype.shuffle_sta = function() {
   return this.map(function(a){ return [a, Math.random()] })
              .sort(function(a, b){ return a[1] - b[1] })
              .map(function(a){ return a[0] });
}
Start seconds.

結論

このように、Schwartzian Transformは、コードがわかりやすいものの、20倍におよぶ速度差がある。煩雑に使うのであれば避けるべきかもしれない。

Dan the Array Shuffler