menu
書いてる野郎
orebike@gmail.com
Array の 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
処理ブロックをcollectメソッドに渡してる collectメソッドは配列の各要素に対して処理を行うメソッドになる・・・ 今回だと処理は1行だけ~ これは使われる状況を考えないとわかりにくい
こんな場合を想定すると・・・
a = [3, 2, 1] a.sort_by do |b| b end
yeildはこのように定義されるので、そして collect は各配列に処理されるので i には 3,2,1 が順に入ることになる
def yeild(b) b end
つまりcollectメソッドは
[3, 3] [2, 2] [1, 1]
というメソッドを内部で打ち出すことになる
結果を配列として結合するのでまずこうなる
[[3, 3],[2, 2],[1, 1]]
そしてこいつの実行
[[3, 3],[2, 2],[1, 1]].sort {|a,b| a[0] <=> b[0] }
sortメソッドが受け取っている処理ブロックは比較対象を2つとって ⇔ メソッドで比較してます つまり処理ブロックは-1, 0, 1の値のリターンを期待しています 最初の場合
3 <=> 2
このような状況になる。当然関係性は 3 > 2 なので値は 1 結果
[[1, 1],[2, 2],[3, 3]]
という配列が出来上がる
最後に
[[1, 1],[2, 2],[3, 3]].collect! {|i| i[1]}
結合しなおして
[1, 2, 3]
という配列を作るっている・・・確かにソートされた
そこで安定ソートの例を見ると、処理自体に配列を強制的に作ってリターンしている
a = [[1,3],[1,2],[1,1],[2,3],[2,2],[2,1]] i = 0 a = a.sort_by do |b| [b[1], i += 1] end
まず各要素….[1, 3],[1, 2]…を突っ込み その各要素を格納するから
[[3, 1], [1, 3]] [[2, 2], [1, 2]] [[1, 3], [1, 1]]
こうなって最終的にはがっちゃんこで
[[[3, 1], [1, 3]], [[2, 2], [1, 2]], [[1, 3], [1, 1]]]
こうなる そして各要素の先頭要素比較をすることになるので
[3, 1] <=> [2, 2]
こんな比較が行われることになる 配列に対する⇔メソッドは 頭から順に比較していって決着がつくまで評価していくというものなので指定したソート基準値で決まればそれまでだし、そうでなければ次の項目(i += 1で生成した値)で比較を行う。この次の項目っていうのは初期状態の並びを保持しているということなので結果安定ソートになる!
すごい!