どう書く？（重複なし関数）2
注意
読んでも得することはありせん（ここに書いてあることは間違ってます。）
コメントにどこが間違ってあるか書いてくれている人がいます。
元のはじまり
sort_by {rand} だと統計的にわずかに偏りが生じるので、シミュレーションで大量のデータのシャッフルを非常に多数回繰り返すような用途にはまずいと思います
というコメント（引用しているのはコメント内の一部）をしてくれた人がいました。
個人の備忘録程度の意味合いしか持たせていなかったので、コメントがあったことにびっくりです。
どう書く？へ
どう書く？内のコメントの中に説明があるという内容があったのでどう書く？の方にいってみてきます。
分かったことは、フラット表示とネスト表示というリンクが存在して、
- フラット表示の時
- 投稿されたコードのすぐ下にコメントが表示されない
- ネスト表示の時
- 投稿されたコードのすぐ下にコメントが表示される
ということです。
以前見たときには、フラット表示を選択していたために、rubykitchさんのコードにつけられたコメントを見逃していたようです。
コメントがつけられていました。気づきませんでした。
巧みだなあと思ったんですが、ごくわずかの確率でrandが同じ値を返すケースがあるはずで、その場合の要素の並び順はsortの実装によって固定されてしまうから、微妙に偏りが出てくるんじゃないかな、という気もします。
(例えば簡略化のために要素数を2つ、randは0か1しか返さないとして、sortがstableだとすると、可能な4通りの組み合わせのうち(0 1)が3回、(1 0)が1回となる)
現実にはdoubleが重なる確率なんて極めて低いでしょうけど。
どんな感じに偏りが出るのか気になったので調べてみます。
調査
まず、refeでsort_byのリファレンスを見ると
class Array def sort_by self.collect {|i| [yield(i), i] }. sort {|a,b| a[0] <=> b[0] }. collect! {|i| i[1]} end end end
とほぼ同じ動作をします。と、書かれています。（ほぼってところが気になるけど…）
動作自体は、簡単に理解できます。
ようは、配列aにsort_byメソッドを適用する時、yieldに関数fを渡していたとすると、
[f(a[0]),a[0]], [f(a[1]),a[1]] ....
というような配列が生成されて、配列の要素の配列の左側の要素を元にソートされた後、右側だけが取り出されて格納される。（＝sort_by終了)という感じです。
今回の場合
randがyieldに渡されるわけです。
randが同じ数を返す可能性があるのは自明なので省略して、
randが同じ数を返してしまった場合について考えて見ることにします。
もし、コメント内の「sort が stable だとする」が「安定なソート*1がrubyのsortメソッドの実装に使われている」という意味だと解釈して考えてみることにします。
安定であるというのは、
配列aの要素,a[x],a[y]に対して「x < y」であるならば、
ソート後の配列a'でも「a'[x] < a'[y]」の順序が保たれているという意味だと思います。つまり、randで出力された乱数が同じであった場合には、最初にその乱数が出力された要素の方が後に出力された要素よりも、必ず先に来るということなのだと思います。これが、コメント内でいわれている偏りなのだと思います。
そこから考えると、ソートが＊安定でない＊ならば偏りは存在しないように感じます。そして、refeで表示した情報の中には、
Enumerable#sort_byは安定ではありません。(unstable sort)
と書かれています。
ということで、rubykitchさんのコードでも問題が無いように思います。
（すっごい勘違いしていたら、ごめんなさい＞＜）
追記
安定なsortではなかったとしても偏りは生じるようです。
確かかどうかは分かりませんが、
偏りが生じる可能性（ある > ない）なようです。
さらに追記
この記事は間違ってます。膨大な数を投入した場合偏りが生じる可能性がすごい高いです。
