public
Last active

  • Download Gist
benchmark.rb
Ruby
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
# user system total real
# real_bsearch best-case 0.370000 0.000000 0.370000 ( 0.367332)
# real_bsearch worst-case 6.590000 0.000000 6.590000 ( 6.602298)
# real_recursive_bsearch best-case 0.200000 0.000000 0.200000 ( 0.195659)
# real_recursive_bsearch worst-case 6.950000 0.010000 6.960000 ( 6.958505)
# bsearch best-case 12.000000 0.180000 12.180000 ( 12.200769)
# bsearch worst-case 12.670000 0.180000 12.850000 ( 12.890500)
# recursive_bsearch best-case 32.840000 0.050000 32.890000 ( 32.988642)
# recursive_bsearch worst-case 35.670000 0.100000 35.770000 ( 37.023431)
require 'benchmark'
n = 5_000_000
ar = (1..n).to_a
Benchmark.bm do |x|
%w[real_bsearch real_recursive_bsearch bsearch recursive_bsearch].each do |meth|
x.report("#{meth} best-case") { 100_000.times do; send(meth, n/2, ar); end }
x.report("#{meth} worst-case") { 100_000.times do; send(meth, -1, ar); end }
end
end
bsearch.rb
Ruby
1 2 3 4 5 6 7 8 9 10 11 12 13 14
def bsearch(needle, haystack)
return nil unless needle && haystack
return nil unless %w![] empty? each!.all? {|op| haystack.respond_to?(op)}
return nil unless needle.respond_to?("<=>")
return nil if haystack.empty?
valid_range = haystack
loop do
return false if valid_range.empty?
mid = valid_range.size / 2
return needle if valid_range[mid] == needle
r = valid_range[mid] > needle ? 0...mid : mid+1..-1
valid_range = valid_range[r]
end
end
o_log_n_bsearch.rb
Ruby
1 2 3 4 5 6 7 8 9
def real_bsearch(needle, haystack)
left, right = [0, haystack.size - 1]
loop do
return false if right < left
mid = (right - left) / 2 + left
return needle if haystack[mid] == needle
(left, right) = haystack[mid] > needle ? [left, mid - 1] : [mid + 1, right]
end
end
o_log_n_r_bsearch.rb
Ruby
1 2 3 4 5 6 7
def real_recursive_bsearch(needle, haystack, left=0, right=haystack.size-1)
return false if right < left
mid = (right - left) / 2 + left
return needle if haystack[mid] == needle
(left, right) = haystack[mid] > needle ? [left, mid - 1] : [mid + 1, right]
real_recursive_bsearch(needle, haystack, left, right)
end
r_bsearch.rb
Ruby
1 2 3 4 5 6 7 8 9 10 11 12
def recursive_bsearch(needle, haystack)
return nil unless needle && haystack
return nil unless %w![] empty? each!.all? {|op| haystack.respond_to?(op)}
return nil unless needle.respond_to?("<=>")
return false if haystack.empty?
mid = haystack.size / 2
return needle if haystack[mid] == needle
range = haystack[mid] > needle ? 0...mid : mid+1..-1
return recursive_bsearch(needle, haystack[range])
end
tests.rb
Ruby
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42
# Loaded suite /Users/kastner/Development/Ruby/junk/bsearch
# Started
# ....
# Finished in 1.770907 seconds.
#
# 4 tests, 16412 assertions, 0 failures, 0 errors
 
require 'test/unit'
METHODS = %w!bsearch recursive_bsearch real_bsearch real_recursive_bsearch!
 
class TestIt < Test::Unit::TestCase
def assert_all(n, h, m="")
METHODS.each do |meth|
assert send(meth, n, h) == n, m
end
end
def assert_none(n, h, m="")
METHODS.each do |meth|
assert !send(meth, n, h), m
end
end
def test_simple
assert_all 1, [1, 2, 3]
end
def test_empty
assert_none 1, []
end
def test_three_elements
assert_all 1, [1, 2, 3]
assert_all 2, [1, 2, 3]
assert_all 3, [1, 2, 3]
assert_none 4, [1, 2, 3]
assert_none -1, [1, 2, 3]
end
def test_lots
tests = `curl -s http://www.mac-guyver.com/switham/2010/04/Binary_Search/tests.txt.gz | zcat`
tests.scan(/(P.+?)\n(.+?)\nin \[\n([^\]]*)\]\? (yes|no)/m).each do |m|
method = m[-1] == "yes" ? :assert_all : :assert_none
send method, m[1].to_i, m[2].split("\n").map {|l| l.to_i}, m[0]
end
end
end

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.