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:
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.
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.
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).
15 comments
[ 3.7 ms ] story [ 51.7 ms ] threadNo, really. I want to know this one. It's almost like we want to encourage people writing slow code...
http://stackoverflow.com/questions/7436155/rubyindex-method-...
That being said, binary search is a welcome addition.
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.
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.
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...
bgcolor is now #717171, which is just crazy. Anything below #444 is just harmful for the eyes.
Looks like a solid release.