Repository navigation
Not correct comparing #29
Description
Activity
bsearch doesn't work for shuffled array:
2.1.4 :014 > a = [6, 5, 4, 10, 7, 1, 9, 3, 0, 8, 2] => [6, 5, 4, 10, 7, 1, 9, 3, 0, 8, 2] 2.1.4 :012 > a.find { |x| x > 7 } => 10 2.1.4 :013 > a.bsearch { |x| x > 7 } => nil
From docs http://ruby-doc.org//core-2.1.5/Array.html#method-i-bsearch
You can use this method in two use cases: a find-minimum mode and a find-any mode. In either case, the elements of the array must be monotone (or sorted) with respect to the block.
This article also states this:
https://blog.engineyard.com/2015/five-ruby-methods-you-should-be-usingHowever, there is a pretty big catch involved with using bsearch: the array must be sorted.
I agree with u, but in this case bsearch and find comparing makes no sence. In worst case bsearch will take much more time then find. It should be pointed in readme I think
I wouldn't say much worse if we compare worst case for find and bsearch:
Worst for bsearch (find element 1):
Benchmark.ips do |x| x.report('find') { data.find { |n| n == 1 } } x.report('bsearch') { data.bsearch { |n| 1 <=> n } } x.compare! end Comparison: find: 1679737.4 i/s bsearch: 451086.6 i/s - 3.72x slower
Now make it worst for find:
Benchmark.ips do |x| x.report('find') { data.find { |n| n == 50_000_000 } } x.report('bsearch') { data.bsearch { |n| 50_000_000 <=> n } } x.compare! end Comparison: bsearch: 3994879.1 i/s find: 0.3 i/s - 15284679.72x slower
I meant that this benchmark is fair enough only for sorted arrays and it will be great if it will be pointed in readme. There're tons of coders who will use bsearch against find in any cases after reading this benchmarks.
Wow. I came here to post about a thought I had that maybe using a smaller array would tilt things in favour of find, but when I tested it, bsearch still blows find away! Amazing!
I consider it's not correct to compare bsearch with find on sorted array. There will be not so much difference between searching in shuffled array.