Floyd–Rivest 对比 Introselect 算法性能
Floyd–Rivest vs. Introselect algorithm performance
Google帮不了我所以就这样了：FloydRivest 算法和 Introselect 这两种选择算法中哪一个具有更好的性能。
我假设它是 FloydRivest 算法，但想要 100% 确定。
此外，如果有更好的算法可用于此目的，我将很高兴听到它们。
TLDR；我觉得 Floyd-Rivest 更好
我最近为我正在进行的项目做了一些关于 selection 算法的研究。下面是每个算法的基本描述：
- Introselect: 执行数据的双分区，使用一个主元。最初，选择一个简单的枢轴（例如中间、3 的中位数等）。简单主元在最坏情况下通常为 O(n^2)，但平均为 O(n)。如果递归级别超过某个阈值，我们将回退到中位数枢轴。这计算成本更高，但保证 O(n) 最坏情况。
- Floyd-Rivest：执行数据的五元分区，有两个主元。选择两个枢轴，以便第 k 个元素位于它们之间，概率很高（这涉及随机采样数据，并通过递归 selecting 两个元素，在第 n 个元素的上方和下方）。当分区的大小变得足够小时，我们 select 使用更简单的方法（例如中位数 3 等）
如您所见，两者非常相似。 Introselect 从简单的枢轴开始，然后退回到复杂的枢轴； Floyd-Rivest 算法恰恰相反。主要区别在于 introselect 使用中位数中位数，而 Floyd-Rivest 使用递归采样技术。所以，我认为更好的比较是中位数与 Floyd-Rivest。
哪个更好？根据我的研究，Floyd-Rivest 的隐藏常数似乎小于中位数的中位数。如果我没记错的话，中位数中位数需要 5n 比较（最坏情况），而 Floyd-Rivest 只需要 3.5n。 Floyd-Rivest 还使用五元方案，当数据可能有很多重复项时这种方案更好。 introselect 和 Floyd-Rivest 都针对小输入简化为相同的算法，所以你应该在那里获得相似的性能（只要你实现它们相同）。在我的测试中，Floyd-Rivest 比我尝试过的所有其他 selection 算法快 20% 以上。不过，我必须承认，我没有针对 introselect 的正确实现进行测试，该实现回退到中位数的中位数（我只是测试了 libstdc++ 的伪 introselect）。在最初的 Floyd-Rivest 论文中，他们自己（他们是中位数方法的合著者）说中位数中位数 "is hardly practical"，并且Floyd-Rivest 算法是 "probably the best practical choice".
所以，在我看来，Floyd-Rivest 的旋转技术比中位数更好。您可以使用 Floyd-Rivest 的旋转实现 introselect，但您也可以只执行纯 Floyd-Rivest 算法。我会推荐 Floyd-Rivest 作为最好的 select离子方法。
注意！ 最初的 Floyd-Rivest 论文给出了他们算法的示例实现（这是在撰写本文时维基百科上列出的实现）。然而，这是一个简化版本。从我的测试来看，简化版实际上很慢！如果你想要一个快速的实现，我认为你需要实现完整的算法。我推荐阅读 Krzysztof C. Kiwiel 的论文 "On Floyd and Rivest's SELECT algorithm"。他很好地描述了如何实现快速的 Floyd-Rivest selection。
Google帮不了我所以就这样了：FloydRivest 算法和 Introselect 这两种选择算法中哪一个具有更好的性能。
我假设它是 FloydRivest 算法，但想要 100% 确定。
此外，如果有更好的算法可用于此目的，我将很高兴听到它们。
TLDR；我觉得 Floyd-Rivest 更好
我最近为我正在进行的项目做了一些关于 selection 算法的研究。下面是每个算法的基本描述：
- Introselect: 执行数据的双分区，使用一个主元。最初，选择一个简单的枢轴（例如中间、3 的中位数等）。简单主元在最坏情况下通常为 O(n^2)，但平均为 O(n)。如果递归级别超过某个阈值，我们将回退到中位数枢轴。这计算成本更高，但保证 O(n) 最坏情况。
- Floyd-Rivest：执行数据的五元分区，有两个主元。选择两个枢轴，以便第 k 个元素位于它们之间，概率很高（这涉及随机采样数据，并通过递归 selecting 两个元素，在第 n 个元素的上方和下方）。当分区的大小变得足够小时，我们 select 使用更简单的方法（例如中位数 3 等）
如您所见，两者非常相似。 Introselect 从简单的枢轴开始，然后退回到复杂的枢轴； Floyd-Rivest 算法恰恰相反。主要区别在于 introselect 使用中位数中位数，而 Floyd-Rivest 使用递归采样技术。所以，我认为更好的比较是中位数与 Floyd-Rivest。
哪个更好？根据我的研究，Floyd-Rivest 的隐藏常数似乎小于中位数的中位数。如果我没记错的话，中位数中位数需要 5n 比较（最坏情况），而 Floyd-Rivest 只需要 3.5n。 Floyd-Rivest 还使用五元方案，当数据可能有很多重复项时这种方案更好。 introselect 和 Floyd-Rivest 都针对小输入简化为相同的算法，所以你应该在那里获得相似的性能（只要你实现它们相同）。在我的测试中，Floyd-Rivest 比我尝试过的所有其他 selection 算法快 20% 以上。不过，我必须承认，我没有针对 introselect 的正确实现进行测试，该实现回退到中位数的中位数（我只是测试了 libstdc++ 的伪 introselect）。在最初的 Floyd-Rivest 论文中，他们自己（他们是中位数方法的合著者）说中位数中位数 "is hardly practical"，并且Floyd-Rivest 算法是 "probably the best practical choice".
所以，在我看来，Floyd-Rivest 的旋转技术比中位数更好。您可以使用 Floyd-Rivest 的旋转实现 introselect，但您也可以只执行纯 Floyd-Rivest 算法。我会推荐 Floyd-Rivest 作为最好的 select离子方法。
注意！ 最初的 Floyd-Rivest 论文给出了他们算法的示例实现（这是在撰写本文时维基百科上列出的实现）。然而，这是一个简化版本。从我的测试来看，简化版实际上很慢！如果你想要一个快速的实现，我认为你需要实现完整的算法。我推荐阅读 Krzysztof C. Kiwiel 的论文 "On Floyd and Rivest's SELECT algorithm"。他很好地描述了如何实现快速的 Floyd-Rivest selection。