See Also
・Kernel#test が便利
・rubyのsort_by / shuffle から学ぶシュワルツ変換とフィッシャー - イェーツのシャッフル
pretty-print - うんたらかんたらRuby - Rubyistで
何よsortとsort_byって
となったので調べてみた。
参考URL:
Enumerable - Rubyリファレンスマニュアル
安定ソート
と、その前にこれが理解できてないのでこっちを整理。
Enumerable#sort は安定ではありません (unstable sort)。
Enumerable#sort_by は安定ではありません (unstable sort)。
註: 比較結果が同じ要素は元の順序通りに並ぶソートを 「安定なソート (stable sort)」と言います。
リファレンス読んでも、パッと理解できなかったので
安定ソート - Wikipediaを見て納得。
安定ソート(あんていソート、stable sort)とは、ソート(並び替え)のアルゴリズムのうち、
同等なデータのソート前の順序が、ソート後も保存されるものをいう。
つまり、ソート途中の各状態において、常に順位の位置関係を保っていることをいう。
たとえば、学生番号順に整列済みの学生データを、テストの点数順で安定ソートを用いて並べ替えたとき、
ソート後のデータにおいて、同じ点数の学生は学生番号順で並ぶようになっている。
2次元配列を使って確認。
(要素1には乱数、要素2にはindexを入れた配列を20個用意して、要素1でソート)
irb(main):001:0> ary = [] => [] irb(main):002:0> 1.upto(20) {|v| ary << [rand(v), v] } => 1 irb(main):003:0> p ary [[0, 1], [0, 2], [2, 3], [1, 4], [3, 5], [0, 6], [5, 7], [3, 8], [3, 9], [3, 10], [4, 11], [11, 12], [12, 13], [11, 14], [6, 15], [4, 16], [2, 17], [11, 18], [16, 19], [2, 20]] => nil irb(main):004:0> ary.sort {|x,y| x[0] <=> y[0]} => [[0, 1], [0, 2], [0, 6], [1, 4], [2, 17], [2, 3], [2, 20], [3, 8], [3, 9], [3, 5], [3, 10], [4, 16], [4, 11], [5, 7], [6, 15], [11, 12], [11, 18], [11, 14], [12, 13], [16, 19]] irb(main):005:0> ary.sort_by{|x| x[0]} => [[0, 1], [0, 2], [0, 6], [1, 4], [2, 17], [2, 3], [2, 20], [3, 8], [3, 9], [3, 5], [3, 10], [4, 16], [4, 11], [5, 7], [6, 15], [11, 12], [11, 18], [11, 14], [12, 13], [16, 19]]
要素1(乱数)でソートされているものの、要素2(index)ではソートされていない。
なるほどこういうことなんですね。
実は安定ソートが書ける
リファレンスに記載されてる通りなんだけど
irb(main):010:0 i = 0 => 0 irb(main):011:0> ary.sort_by {|v| [v[0], i += 1] } => [[0, 1], [0, 2], [0, 6], [1, 4], [2, 3], [2, 17], [2, 20], [3, 5], [3, 8], [3, 9], [3, 10], [4, 11], [4, 16], [5, 7], [6, 15], [11, 12], [11, 14], [11, 18], [12, 13], [16, 19]]
おお、できた。
ちなみに、sortをブロック無しで使うと
irb(main):012:0> ary.sort => [[0, 1], [0, 2], [0, 6], [1, 4], [2, 3], [2, 17], [2, 20], [3, 5], [3, 8], [3, 9], [3, 10], [4, 11], [4, 16], [5, 7], [6, 15], [11, 12], [11, 14], [11, 18], [12, 13], [16, 19]]
安定してるように見えるけど、実際には小さい配列の2つの要素を比較してるからなんでしょう。
sortとsort_byの違い
さぁ、ここでようやく本題。
リファレンスのようにdowncaseを呼び出す例を考えると
sortは比較の度に呼び出してしまうため
呼び出すメソッドや要素数によってはボトルネックになってしまう。
一方sort_byでは、要素1にブロック(downcase)の値、
要素2に元(downcase前)の値を持つ2次元配列を生成し、
要素1でソートをしておいて要素2の値を返す。
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
なのでdowncaseの評価回数は要素数と同じになる。
ということらしい。
なるほど。
実行例
irb(main):001:0> class Integer irb(main):002:1> def count irb(main):003:2> $n += 1 irb(main):004:2> self irb(main):005:2> end irb(main):006:1> end irb(main):007:0> 1.upto(20) {|v| ary << [rand(v), v] } => 1 irb(main):010:0> $n = 0 ary.sort {|x,y| x[0].count <=> y[0].count} irb(main):012:0> p $n 114 irb(main):017:0> ary.sort_by{|x| x[0].count} irb(main):018:0> p $n 20