Created
April 25, 2010 23:54
-
-
Save kastner/378840 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# One possible bug is that each element in haystack doesn't | |
# respond to the comparison operators. | |
# That can be fixed by doing | |
# return nil unless haystack.all? {|e| e.respond_to?("<=>")} | |
# but that takes a LOG(2)N algo and makes it N * LOG(2)N | |
# since the requirement is a "sorted array", that implies that each | |
# element is comparable. | |
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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
require 'test/unit' | |
class TestIt < Test::Unit::TestCase | |
def assert_both(n, h, m="") | |
assert bsearch(n, h) == n, m | |
assert recursive_bsearch(n, h) == n, m | |
end | |
def assert_neither(n, h, m="") | |
assert !bsearch(n, h), m | |
assert !recursive_bsearch(n, h), m | |
end | |
def test_simple | |
assert_both 1, [1, 2, 3] | |
end | |
def test_empty | |
assert_neither 1, [] | |
end | |
def test_three_elements | |
assert_both 1, [1, 2, 3] | |
assert_both 2, [1, 2, 3] | |
assert_both 3, [1, 2, 3] | |
assert_neither 4, [1, 2, 3] | |
assert_neither -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_both : :assert_neither | |
send method, m[1].to_i, m[2].split("\n").map {|l| l.to_i}, m[0] | |
end | |
end | |
end |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment