ffakerのsourceを眺めていたら以下のようなコードがありました。
# ffaker-2.1.0/lib/ffaker/utils/array_utils.rb module FFaker module ArrayUtils def self.shuffle(array) array.sort_by{Kernel.rand} end
これ自体は、Array#shuffleがない頃のrubyでshuffleさせるためのものですが
意味は分かりやすいし読みやすいのですが、
ふと sort_by {rand} という書き方に一瞬、あれ?これどうなってるんだっけと
思ってしまいました。
シュワルツ変換
randの結果を突っ込んだ「tupleを生成してsortして、tupleにした元の結果を返す」
というアルゴリズムです。
これをSchwartzian Transform と言います。
シュワルツ(シュウォーツ)変換 (Schwartzian Transform) : Serendip - Webデザイン・プログラミング
stack overflowでの解説
How does Ruby's sort_by {rand} work? - Stack Overflow
このroughなrubyコードを用いた説明がわかりやすいです。
そして、最後にArray#shuffle!はFisher-Yatesを用いてより最適化してまっせと教えてくれてます。
Fisher-Yates shuffle
Programming Place Plus アルゴリズムとデータ構造編【その他】 第2章 ランダムシャッフル
こちらの解説がわかりやすかったです。
配列全体の中から1つの要素をランダムで選び出し、 これを末尾の要素と交換することを繰り返します。 ここで、"末尾" の位置は、交換を行うごとに1つずつ手前へ移動していきます。 言い換えれば、後ろの方から確定させていくということになります。
sorce
ruby2.3.0
> $ Array#shuffle! From: array.c (C Method): Owner: Array Visibility: public Number of lines: 29 static VALUE rb_ary_shuffle_bang(int argc, VALUE *argv, VALUE ary) { VALUE *ptr, opts, *snap_ptr, randgen = rb_cRandom; long i, snap_len; if (OPTHASH_GIVEN_P(opts)) { randgen = rb_hash_lookup2(opts, sym_random, randgen); } if (argc > 0) { rb_raise(rb_eArgError, "wrong number of arguments (%d for 0)", argc); } rb_ary_modify(ary); i = RARRAY_LEN(ary); ptr = RARRAY_PTR(ary); snap_len = i; snap_ptr = ptr; while (i) { long j = RAND_UPTO(i); VALUE tmp; if (snap_len != RARRAY_LEN(ary) || snap_ptr != RARRAY_PTR(ary)) { rb_raise(rb_eRuntimeError, "modified during shuffle"); } tmp = ptr[--i]; ptr[i] = ptr[j]; ptr[j] = tmp; } return ary; }
このwhileのとこですね。