弗洛伊德-里维斯特算法与Introselect算法的表现比较

Question

弗洛伊德-里维斯特算法与Introselect算法的表现比较

performancealgorithmselectiontime-complexityspace-complexity

9

谷歌无法帮助我，所以这是我的翻译：在两个选择算法FloydRivest算法和Introselect中，哪一个性能更好。我认为是FloydRivest算法，但想要100％确定。如果存在更好的算法，我很乐意了解它们。

- user2340939

1

如果你有真实的数据，那么就拿出两个实现并进行测试。这两个算法具有相似的大O时间和空间复杂度；然而，两个O(n)算法在实现和提供的数据不同的情况下仍然可能表现出非常不同的性能。这就是为什么你会发现很少有关于“X是最好的”的参考资料 - 这取决于具体情况。 - tucuxi

@tucuxi，我认为你应该将你的评论扩展成一个答案。 - Anshul Goyal

@tucuxi，你说的我都知道，所以我才会问这个具体的问题，这样我就不需要浪费时间实现它们两个。而且，我对一个平均/现实世界的情况很感兴趣。 - user2340939

2

您IP地址为143.198.54.68，由于运营成本限制，当前对于免费用户的使用频率限制为每个IP每72小时10次对话，如需解除限制，请点击左下角设置图标按钮（手机用户先点击左上角菜单按钮）。 - tucuxi

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Azmisov · Accepted Answer

TLDR; 我认为Floyd-Rivest更好。

最近我在研究选择算法，因为有一个项目需要用到。以下是每个算法的基本描述：

- Introselect：使用单个中心轴对数据进行双分区。最初选择简单的中心轴（例如中间值、三数中位数等）。简单的中心轴在最坏情况下通常是O(n^2)，但平均情况下是O(n)。如果递归级别超过某个阈值，就会回退到中位数中的中位数中心轴。这样计算成本更高，但保证了最坏情况下的O(n)。 - Floyd-Rivest：使用两个中心轴对数据进行五分区。选择两个中心轴，使得第k个元素以高概率位于它们之间（这涉及随机抽样数据，并通过递归选择上下文中的两个元素，超过第n个元素）。当分区大小变得足够小时，我们使用更简单的方法选择中心轴（例如中位数、三数中位数等）。

如您所见，两者非常相似。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的论文“关于Floyd和Rivest的SELECT算法”。他对如何实现快速的Floyd-Rivest选择算法给出了相当好的描述。