Hatena::Grouprubyist

うんたらかんたらRuby RSSフィード

2009-02-23sortとsort_by

sortとsort_by

| sortとsort_by - うんたらかんたらRuby を含むブックマーク はてなブックマーク - sortとsort_by - うんたらかんたらRuby

pretty-print - うんたらかんたらRuby - Rubyist

何よsortsort_byって

となったので調べてみた。


参考URL

Enumerable - Rubyリファレンスマニュアル


安定ソート

と、その前にこれが理解できてないのでこっちを整理。

Enumerable#sort は安定ではありません (unstable sort)。

Enumerable#sort_by は安定ではありません (unstable sort)。

註: 比較結果が同じ要素は元の順序通りに並ぶソートを 「安定なソート (stable sort)」と言います。

リファレンス読んでも、パッと理解できなかったので

安定ソート - Wikipediaを見て納得。


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つの要素を比較してるからなんでしょう。



sortsort_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
トラックバック - http://rubyist.g.hatena.ne.jp/rochefort/20090223