Skip to content

Instantly share code, notes, and snippets.

@pocke
Created Nov 27, 2014
Embed
What would you like to do?
Array#include?, Array#bsearch, Set#include? benchmark
require 'benchmark'
require 'set'
profile_init = false
def search_array(array, target)
array.include?(target)
end
def search_sorted_array(array, target)
array.bsearch do |x|
x >= target
end == target
end
def search_set(set, target)
set.include?(target)
end
testcases = [1..2000, 1..20000, 1..200000, 1..2000000].map(&:to_a)
testcases.each do |target_source|
array_time = 0
sorted_time = 0
set_time = 0
sort_time = 0
set_init_time = 0
testcase = target_source.select(&:even?)
set = testcase.to_set
100.times do
shuffled = testcase.shuffle
target = target_source.sample
array_time += Benchmark.realtime do
search_array(shuffled, target)
end
sort_time += Benchmark.realtime do
shuffled.sort
end if profile_init
sorted_time += Benchmark.realtime do
search_sorted_array(testcase, target)
end
set_init_time += Benchmark.realtime do
set = testcase.to_set
end if profile_init
set_time += Benchmark.realtime do
search_set(set, target)
end
end
puts "Testcase size: #{testcase.size}"
puts "Array#include?: #{'%.8f' % array_time}s"
puts "Array#bsearch: #{'%.8f' % sorted_time}s"
puts "Set#include?: #{'%.8f' % set_time}s"
if profile_init
puts '-------------'
puts "Sort Init: #{'%.8f' % sort_time}s"
puts "Set Init: #{'%.8f' % set_init_time}s"
end
puts;puts
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment