5 ms·
Ruby 2.0.0 in Detail
- Justsignedup 14y agoWhy 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...
- stephenhuey 14y agoMaybe 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-vs-binary-search http://stackoverflow.com/questions/7436155/rubyindex-method-... That being said, binary search is a welcome addition.
- ajanuary 14y agoI 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.
- Hinrik 14y agoFor 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.
- rraval 14y agoPython: http://docs.python.org/2/library/bisect.html http://docs.python.org/2/library/bisect.html
- pmahoney 14y agoPart 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.
- kylebgorman 14y agoA 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 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...
- fusiongyro 14y agoIt'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).
- kylebgorman 14y agoPython has the stdlib module "bisect" which does binary search.
- alexvay 14y agoThe colors of the site are _terrible_ on the eyes!
- ajanuary 14y agoIt 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)
- timblair 14y agoFixed. Sorry about that.
- pooriaazimi 14y agoAnd please join http://contrastrebellion.com/ 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.
- VeejayRampay 14y agoAwesome write-up, thanks for putting the work in for everyone. Looks like a solid release.
- moron4hire 14y agoRefinements look exactly like C# Extension Methods.