performance - Floyd–Rivest 对比 Introselect 算法性能

Question

Google 帮不了我，所以就这样吧:FloydRivest 算法和 Introselect 这两种选择算法中哪一种具有更好的性能。

我假设它是 FloydRivest 算法，但要 100% 确定。

此外，如果存在用于此目的的更好算法，我将很高兴听到它们。

Answer 1

TLDR；我认为 Floyd-Rivest 更好

我最近为我正在从事的项目做了一些关于选择算法的研究。以下是每个算法的基本描述:

• Introselect:使用单个主元对数据进行二分。最初，选择一个简单的枢轴(例如中间、3 的中位数等)。简单主元在最坏情况下通常为 O(n^2)，但平均为 O(n)。如果递归级别超过某个阈值，我们将回退到中位数枢轴。这计算成本更高，但保证 O(n) 最坏情况。
• Floyd-Rivest:执行数据的五元分区，有两个主元。选择两个枢轴使得第 k 个元素很有可能位于它们之间(这涉及随机采样数据，并通过递归选择两个元素，高于和低于第 n 个元素)。当分区的大小变得足够小时，我们使用更简单的方法(例如，3 的中位数等)选择枢轴

如您所见，两者非常相似。 Introselect 从简单的枢轴开始，然后退回到复杂的枢轴； Floyd-Rivest 算法恰恰相反。主要区别在于 introselect 使用中位数中位数，而 Floyd-Rivest 使用递归采样技术。所以，我认为更好的比较是中位数与 Floyd-Rivest。

哪个更好？根据我的研究，Floyd-Rivest 的隐藏常数似乎小于中位数的中位数。如果我没记错的话，中位数中位数需要类似 5n 的比较(最坏情况)，而 Floyd-Rivest 只需要 3.5n。 Floyd-Rivest 还使用五元方案，当数据可能有很多重复项时这种方案更好。 introselect 和 Floyd-Rivest 都针对小输入缩减为相同的算法，因此您应该在那里获得相似的性能(只要您实现相同)。在我的测试中，Floyd-Rivest 比我尝试过的所有其他选择算法快 20% 以上。不过，我必须承认，我没有针对回落到中位数中位数的 introselect 的正确实现进行测试(我只是测试了 libstdc++ 的伪 introselect)。在最初的 Floyd-Rivest 论文中，他们自己(他们是中位数中位数方法的合著者)说中位数中位数“几乎不实用”，并且 Floyd-Rivest算法是“可能是最佳实用选择”。

因此，在我看来，Floyd-Rivest 的旋转技术优于中位数。您可以使用 Floyd-Rivest 的旋转来实现 introselect，但是您也可以只执行纯 Floyd-Rivest 算法。我会推荐 Floyd-Rivest 作为最佳选择方法。

注意!最初的 Floyd-Rivest 论文给出了他们算法的示例实现(这是在撰写本文时维基百科上列出的实现)。然而，这是一个简化版本。从我的测试来看，简化版实际上很慢!如果你想要一个快速的实现，我认为你需要实现完整的算法。我推荐阅读 Krzysztof C. Kiwiel 的论文“On Floyd and Rivest's SELECT algorithm”。他很好地描述了如何实现快速 Floyd-Rivest 选择。