背景
自分で Ruby のコードを書いていて、Array に対して「重複を取り除いて昇順に並び替えたい」ってときがある。たとえば Rails 製アプリを運用していて、特定の条件を満たす User モデルのレコードの id の一覧を取り出すときとか。
そんで、なんとなくいつものように array.uniq.sort といったコードを書いていて、ふと思った。これ array.sort.uniq って書くのとどっちがいいんだろう。uniq と sort の順番を替えたときに、実行速度に影響があったりするんかな。影響しそう。
と思ったので、ベンチマークを取った。
測定コード
require "benchmark"
array = Array.new
1_0000_0000.times do
array << rand(100)
end
puts ".sort.uniq"
puts Benchmark.realtime { array.sort.uniq }
puts ".uniq.sort"
puts Benchmark.realtime { array.uniq.sort }
0〜99の整数を要素に、長さ1億の配列を作って試した。
めっちょ余談だけど、桁の大きい整数を3桁区切りで表示されてもぜんぜん頭に入ってこない、ぼくは4桁区切りじゃないとだめだ。英語圏の人だと3桁区切りがいいんですかねぇ。
結果
ちなみに Ruby 2.2.0 で実行した。
.sort.uniq
13.716189389000647
.uniq.sort
3.5271070249982586
はい
先に uniq してから sort した方がよさそう。なんとなくそう書いていたけれど、最初に要素数を減らしてから並び替えるといい、ということか。実装を確認して追記したい。
試しに GitHub のリポジトリを検索してみると… (結果の件数は2015年2月4日14:00頃のもの)
- Search · ".uniq.sort" 36,935件
- Search · ".sort.uniq" 20,756件
ここでは立て続けにチェインして呼び出している場合しか検索できていないけれど、これを見る限りでは uniq してから sort しているコードの方が多いっぽい。逆に sort してから uniq した方が有効な場面ってあるのかな。今のところ思い付いていない。