[#37730] [Ruby 1.9 - Bug #4962][Open] come back gem_prelude! — Yusuke Endoh <mame@...>

24 messages 2011/07/02

[#37840] [Ruby 1.9 - Feature #4985][Open] Add %S[] support for making a list of symbols — Aaron Patterson <aaron@...>

23 messages 2011/07/07

[#37866] [Backport87 - Feature #4996][Open] About 1.8.7 EOL — Shyouhei Urabe <shyouhei@...>

22 messages 2011/07/08

[#37913] [Ruby 1.9 - Bug #5003][Open] Enumerator#next segfaults in OS X Lion (10.7) — Ganesh Gunasegaran <ganesh.gunas@...>

16 messages 2011/07/09

[#37917] [Ruby 1.9 - Feature #5005][Open] Provide convenient access to original methods — Lazaridis Ilias <ilias@...>

13 messages 2011/07/09

[#37932] [Ruby 1.9 - Feature #5008][Open] Equal rights for Hash (like Array, String, Integer, Float) — Suraj Kurapati <sunaku@...>

31 messages 2011/07/09

[#37936] [Ruby 1.9 - Feature #5010][Open] Add Slop(-like) in stdlib and deprecate current OptionParser API — Rodrigo Rosenfeld Rosas <rr.rosas@...>

29 messages 2011/07/09

[#37968] [Ruby 1.9 - Bug #5015][Open] method_added" is called in addition to "method_undefined — Lazaridis Ilias <ilias@...>

14 messages 2011/07/10

[#38096] [Ruby 1.9 - Feature #5033][Open] PATCH: 1.9: gc_mark_children: Avoid gc_mark() tail recursion, use goto again. — Kurt Stephens <ks.ruby@...>

14 messages 2011/07/16

[#38109] [Ruby 1.9 - Bug #5034][Open] C Source Code formatting — Lazaridis Ilias <ilias@...>

18 messages 2011/07/16

[#38171] [Ruby 1.9 - Bug #5047][Open] Segfault (most likely involving require) — Jack Christensen <jack@...>

21 messages 2011/07/18

[#38182] [Ruby 1.9 - Feature #5054][Open] Compress a sequence of ends — ANDO Yasushi ANDO <andyjpn@...>

68 messages 2011/07/19

[#38197] [Ruby 1.9 - Feature #5056][Open] About 1.9 EOL — Shyouhei Urabe <shyouhei@...>

39 messages 2011/07/19
[#38900] [Ruby 1.9 - Feature #5056] About 1.9 EOL — Shota Fukumori <sorah@...> 2011/08/10

[#38902] Re: [Ruby 1.9 - Feature #5056] About 1.9 EOL — Yukihiro Matsumoto <matz@...> 2011/08/10

Hi,

[#39048] Re: [Ruby 1.9 - Feature #5056] About 1.9 EOL — SASADA Koichi <ko1@...> 2011/08/22

Hi,

[#39055] Re: [Ruby 1.9 - Feature #5056] About 1.9 EOL — Lucas Nussbaum <lucas@...> 2011/08/23

On 23/08/11 at 06:50 +0900, SASADA Koichi wrote:

[#38295] [Ruby 1.9 - Feature #5064][Open] HTTP user-agent class — Eric Hodel <drbrain@...7.net>

15 messages 2011/07/21

[#38391] [Ruby 1.9 - Bug #5076][Open] Mac OS X Lion Support — Yui NARUSE <naruse@...>

17 messages 2011/07/22

[#38503] [Ruby 1.9 - Feature #5096][Open] offer Logger-compatibility for ext — Eric Wong <normalperson@...>

16 messages 2011/07/25

[#38510] [Ruby 1.9 - Feature #5097][Assigned] Supported platforms of Ruby 1.9.3 — Yui NARUSE <naruse@...>

42 messages 2011/07/26

[#38526] [Backport92 - Backport #5099][Open] Backport r31875 load path performance problem — Aaron Patterson <aaron@...>

19 messages 2011/07/26

[#38538] [Ruby 1.9 - Feature #5101][Open] allow optional timeout for TCPSocket.new — Eric Wong <normalperson@...>

15 messages 2011/07/27

[#38610] [Ruby 1.9 - Feature #5120][Open] String#split needs to be logical — Alexey Muranov <muranov@...>

18 messages 2011/07/30

[#38623] [Ruby 1.9 - Feature #5123][Open] Alias Hash 1.9 as OrderedHash — Alexey Muranov <muranov@...>

14 messages 2011/07/31

[ruby-core:38149] Re: [Ruby 1.9 - Feature #4766] Range#bsearch

From: Michael Edgar <adgar@...>
Date: 2011-07-18 00:12:51 UTC
List: ruby-core #38149
On Jul 17, 2011, at 7:54 PM, Eric Hodel wrote:

> When performing a binary search you may have multiple matching values, the three 100 values from the example.  For the proposed implementation the first one is chosen for consistency.
> 
> Nobody knows what the #beach method you keep talking about would be.  Maybe you mean binary-search-each?  That doesn't make any sense as binary search will not yield each item in the enumerator.

I wouldn't say "nobody". I think what he's suggesting is a more flexible binary-search-each which yields all elements for which the block is true. Hear this out:

The current implementation's result is equivalent to Enumerable#min, except it requires sorted order so it can use binary search. This adds the asymptotic speedup to the #min method.

This is handy, but what if someone wanted the maximum? Or just the first element that matches?

Those are equivalent, respectively, to Enumerable#max and Enumerable#find. Personally, I think I'd usually just want to get the first one that matches, and not use extra cycles computing the minimum. There's room for choice which the current implementation lacks. Further, they can't be built based on the new method. They have to be written from scratch.

These could be implemented with a base, binary_matches method, with selection logic added on. Assume binary_matches takes a block, and returns an enumerator for all elements for which the block yields true. It can do so in O(log(n)) time. This is just a thrown together API, a better API likely exists. If you had such a method, you could implement the existing proposal (min), max, and find as such, giving all the log(n) speedup:

# The current bsearch proposal renamed to bsearch_min.
def bsearch_min(&blk)
  binary_matches(&blk).min
end

# Returns the largest elt for which the block yields true 
def bsearch_max(&blk)
  binary_matches(&blk).max
end

# Returns the first-discovered elt for which the block yields true
def bsearch_find(&blk)
  binary_matches(&blk).each do |elt|
    return elt if blk.call(elt)
  end
end

This seems useful to me.

Michael Edgar
adgar@carboni.ca
http://carboni.ca/

In This Thread