Benchmark: Finding N keys with highest value in hash, keeping order

benchmark-n-best-sentences.rb

require 'benchmark'

def extract1(sentences, n)
  sentences.map(&:reverse).each_with_index
  .sort_by(&:first).reverse
  .take(n)
  .sort_by(&:last)
  .map { |(_,s),_| s }
end

def extract2(sentences, n)
  sentences.to_a.values_at(
  *sentences.values
  .each_with_index
  .sort.reverse
  .map(&:last)
  .sort.take(n))
  .map(&:first)
end

def extract3(sentences, n)
  min = sentences.values.sort[-n]
  a = []
  i = 0
  sentences.each do |k, v|
    if i < n and v <= min
      (a.push(k) and i += 1)
    end
  end
  a
end

def extract4(sentences, n)
  cutoff_val = sentences.values.
  sort.last(n).first
  sentences.select{|k,v| v >= cutoff_val }
end

Benchmark.bm do |x|

  sentences = [
    ['This is the first sentence.',  5],
    ['This is the second sentence.', 1],
    ['This is the last sentence.',   6]
  ]

  x.report do
    100000.times do
      extract1(sentences, 2)
    end
  end


  sentences = {
    'This is the first sentence.' => 5,
    'This is the second sentence.' => 1,
    'This is the last sentence.' => 6
  }

  x.report do
    100000.times do
      extract2(sentences, 2)
    end
  end

  x.report do
    100000.times do
      extract3(sentences, 2)
    end
  end

  x.report do
    100000.times do
      extract4(sentences, 2)
    end
  end

end

#       user     system      total        real
#  0.820000   0.000000   0.820000 (  0.819964)
#  0.850000   0.000000   0.850000 (  0.853231)
#  0.210000   0.000000   0.210000 (  0.210607)
#  0.320000   0.000000   0.320000 (  0.320994)