Ruby＃index方法VS二進制搜索

給定一個元素和一個數組，Ruby＃index方法返回數組中元素的位置。我使用二進制搜索實現了我自己的索引方法，預計我的表現會優於內置索引方法。令我驚訝的是，這個內置的實驗在我的實驗中運行速度約爲我的三倍。Ruby＃index方法VS二進制搜索

任何Rubyist知道原因？

來源

2011-09-15 Terry Li

誰說Ruby'＃index'方法還沒有用二分搜索實現？而且，誰說這個方法是用Ruby實現的呢？ :-) –

@Platinum Azure哦，我看，它可能會用二進制搜索在C中實現。非常感謝！ –

你明白了！ :-) –

內置的#index is not a binary search，它只是一個簡單的迭代搜索。然而，它是用C而不是Ruby來實現的，所以它自然可以快幾個數量級。

來源

2011-09-15 19:30:55 harbichidian

謝謝。不過這真的很奇怪。他們之所以沒有采用二進制搜索方法，有沒有原因？ –

二分法搜索涉及能夠比較兩個元素，而不僅僅是能夠看到兩個元素是否相等。還要注意文檔說它返回* first * object等於參數 - 二進制搜索並不總是返回該元素。此外，我的#bsearch版本（假設數組已排序）似乎並不比#index慢：https://gist.github.com/1220440 –

我假設你的#bsearch實現能夠擊敗Ruby和與二進制搜索和順序搜索之間的C？ –

Ruby＃index方法VS二進制搜索

回答

相關問題