sort + ブロックではなくsort_by + ブロックを使おう

Ruby 2.1.0リファレンスマニュアル Enumerable#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のブロック内では比較対象を作るための処理を何度も呼ぶ必要があり、それが速度低下を引き起こすらしいです。

検証してみました。

bench.rb

require "benchmark"

class Integer
  def piyo
    $n += 1
    self
  end
end

def bench ary
  puts "------------"
  puts "length:#{ary.length}"

  $n = 0
  puts "sort"
  puts Benchmark.realtime { ary.sort {|a, b| a.piyo <=> b.piyo } }
  puts $n

  $n = 0
  puts "sort_by"
  puts Benchmark.realtime { ary.sort_by {|i| i.piyo } }
  puts $n
end

bench(10_000.times.map {|_| rand(100000) })
bench(100_000.times.map {|_| rand(100000) })
bench(1_000_000.times.map {|_| rand(100000) })
bench(10_000_000.times.map {|_| rand(100000) })

$ ruby bench.rb
------------
length:10000
sort
0.028192596999815578
240766
sort_by
0.007100288999936311
10000
------------
length:100000
sort
0.3362468350001109
3072618
sort_by
0.09367915700022422
100000
------------
length:1000000
sort
4.030596262000017
37349434
sort_by
1.0217048670001532
1000000
------------
length:10000000
sort
46.01518444800013
440193772
sort_by
12.482706402000076
10000000

環境は
Core i5 3210M
メモリ4GB
windows8.1上のVirtualboxで動かしているUbuntu14.04
ruby 2.2.0p0
です。

piyoは軽い処理にも関わらず実行時間はsortに比べてsort_byが1/4ほどになっています。

例えばpiyoが10msかかる処理だと、要素数が100でもsort_byの方が10倍程度の速かったです。

結論
sort + ブロックをせずにsort_by + ブロックを使おう。