Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Not correct comparing #29

Closed
nickskalkin opened this issue Mar 5, 2015 · 6 comments

Comments

@nickskalkin
Copy link

commented Mar 5, 2015

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.

@edbond

This comment has been minimized.

Copy link

commented Mar 5, 2015

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 
@edbond

This comment has been minimized.

Copy link

commented Mar 5, 2015

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-using

However, there is a pretty big catch involved with using bsearch: the array must be sorted.

@nickskalkin

This comment has been minimized.

Copy link
Author

commented Mar 5, 2015

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

@edbond

This comment has been minimized.

Copy link

commented Mar 5, 2015

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

see http://bigocheatsheet.com/#searching

@nickskalkin

This comment has been minimized.

Copy link
Author

commented Mar 6, 2015

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.

@hrdwdmrbl

This comment has been minimized.

Copy link

commented Apr 11, 2015

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!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
3 participants
You can’t perform that action at this time.