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二进制搜索

回答

相关问题