Ruby 2.0.0 in Detail | Hacker News Reader

Ruby 2.0.0 in Detail

globaldev.co.uk

63 pointstimblair15 comments

Awesome write-up, thanks for putting the work in for everyone.

Looks like a solid release.

Why was Array#bsearch and Range#bsearch not part of ruby stdlib for 20 years?

No, really. I want to know this one. It's almost like we want to encourage people writing slow code...

Maybe because some friendly contributor such as yourself hadn't added it yet! I have no idea, really, but apparently the Ruby index method drops down to C so it's fairly fast:

http://stackoverflow.com/questions/7436155/rubyindex-method-...

That being said, binary search is a welcome addition.

I did a quick [1] google around some of the most popular programming languages to see if their stdlibs had binary search:

Python: No Perl: No PHP: No Lua: No Java: Yes .NET: Yes Objective-C: Yes

Of course your point then becomes "Why haven't Ruby, Python, Perl, PHP and Lua added binary search".

[1] So it may be wrong. Please correct me if I am.

For Lua at least, it's not surprising. Its standard library is deliberately extremely minimal. There are no functions to search tables (Lua's datastructure for collections), not even linearly.

Python: http://docs.python.org/2/library/bisect.html

Part of it must be that binary search only works on a sorted array, and most arrays won't be sorted.

Followup question: are there other common array operations that only work on arrays in a particular state? Are any of these in or out of various standard libraries?

A long time ago... I implemented a wrapper around the Gnu Scientific Library matrix operations. I recall trying to be clever by mixing in some extra methods only after getting the LU decomposition (these extra methods required the matrix to be in a specific state). A little too dynamic for my current tastes. It's not a terrible idea perhaps, but this sort of thing tends to kill performance.

A good example of an array operation only appropriate for specific states is Python's treatment of heaps:

http://docs.python.org/2/library/heapq.html

You need to heapify(your_array) in place before, e.g., calling nsmallest(your_array). Not saying that it's good style, but...

It's interesting that in Smalltalk there is a SortedCollection class which guarantees this state, and in general you can sort by calling #asSortedCollection on your collection. Presumably the search methods on that class are O(log N) rather than O(N).

Python has the stdlib module "bisect" which does binary search.

Refinements look exactly like C# Extension Methods.

The colors of the site are _terrible_ on the eyes!

It also uses -webkit-text-size-adjust: none; which means you can't zoom in to make the text bigger (I've emailed them about this)

Fixed. Sorry about that.

And please join http://contrastrebellion.com/ and do

    $('article p').css('color','#222')

so we can read the article.

bgcolor is now #717171, which is just crazy. Anything below #444 is just harmful for the eyes.

Reply on news.ycombinator.com