Floyd-Rivest 与 Introselect 算法性能

Question

谷歌无法帮助我，所以它是这样的：两种选择算法，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 论文给出了他们算法的示例实现（这是在撰写本文时在 Wikipedia 上列出的实现）。但是，这是一个简化版本。从我的测试来看，简化版实际上很慢！如果你想要一个快速的实现，我认为你需要实现完整的算法。我建议阅读 Krzysztof C. Kiwiel 的论文“On Floyd 和 Rivest 的 SELECT 算法”。他很好地描述了如何实现快速 Floyd-Rivest 选择。