sort関数によるシャッフルについて、続 - snippets from shinichitomita’s journal

トラックバックしてもらった情報によると、さっきのはSchwartzian Transformと呼ばれるアルゴリズムの応用らしい。

http://blog.livedoor.jp/dankogai/archives/50614134.html

まずは、Fisher-Yates法。コードは最速インターフェース研究会 :: 実践JavaScriptで配列をシャッフルする方法リファクタリングほぼそのまま。
MacBook Pro上のSafariでもFirefox 1.5でも、0.1秒とかからない。

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

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

計算量の話で言うと、Fisher-YatesがO(n)なのに対して、Schwartzian TransformはソートしてるのでO(n log(n))かかるってことですかね。ブラウザのJavaScriptのsort()が内部で何ソートをやってるかは知らないのですが、Safariはバブルソートとかやってるんでしょうかしらね。