Rubyのsort_byを理解する
Rubyのsort_byとsortでどう違うのかわかっていないので調べた。
Rubyのリファレンスマニュアルを読む
リファレンスマニュアルをみると下記のように書いていた。
sort_byの説明
Enumerable#sort と比較して sort_by が優れている点として、比較条件が複雑な場合の速度が挙げられます。 sort_by を使わない以下の例では比較を行う度に downcase が実行されます。 従って downcase の実行速度が遅ければ sort の速度が致命的に低下します。
p ["BAR", "FOO", "bar", "foo"].sort {|a, b| a.downcase <=> b.downcase }
一方、次のように sort_by を使うと downcase の実行回数は要素数と同じです。 つまり、その部分の実行時間は O(n) のオーダーです。
p ["BAR", "FOO", "bar", "foo"].sort_by {|v| v.downcase }
sort_byの挙動
sort_by を使うと downcase の実行回数は要素数と同じというのがわからなかった。
リファレンスには、以下のコードとほぼ同じ動作をします。と書いてあったのでsort_byのコードを読むことにした。
(ユニさんの解説も参考にしています。ありがとうございます。)
class Array
def sort_by
self.map {|i| [yield(i), i] }.
sort {|a, b| a[0] <=> b[0] }.
map {|i| i[1]}
end
end
以下のコードを実行して、sort_byのコードを分解しながらみていくと理解できた。
p ["BAR", "FOO", "bar", "foo"].sort_by {|v| v.downcase }
# => ["BAR", "bar", "FOO", "foo"]
self.map {|i| [yield(i), i] }まで
self.map {|i| [yield(i), i] }では、yield(i)の値とiの値は以下のようになる。
# yield(i)の値 "bar", "foo", "bar", "foo" # (downcaseした値)
# iの値 "BAR", "FOO", "bar", "foo" # (元の配列の値)で
上記を二次元配列にしている。ここまでの返す値
# => [["bar", "BAR"], ["foo", "FOO"], ["bar", "bar"], ["foo", "foo"]]
sort {|a, b| a[0] <=> b[0] }まで
sort {|a, b| a[0] <=> b[0] }では、
["bar", "foo", "bar", "foo"](downcaseした配列)の値を比べてソートしている。
ここまでの返す値
# => [["bar", "BAR"], ["bar", "bar"], ["foo", "FOO"], ["foo", "foo"]]
map {|i| i[1]}まで
map {|i| i[1]}では、
[["bar", "BAR"], ["bar", "bar"], ["foo", "FOO"], ["foo", "foo"]](ソート済みの二次元配列)から、元の要素だけを取り出している。
ここまでの返す値
# => ["BAR", "bar", "FOO", "foo"]
コードをひとつひとつ分解してみると、downcaseの実行回数は要素数と同じというのがわかった。
じゃあsortはいつのタイミングで使うのかという疑問が残ったけどそれはまた今度調べる。
