什么是最被低估或鲜为人知但实用的算法？

Question

我正在寻找一种算法或数据结构，它非常不为人知却又非常有用，以至于你认为计算机科学或编程界对其的忽视是一个可怕的疏漏。如果我们所有人都能学会这个算法，那么未来的许多程序都将得到很大的好处。

我想到的最好的算法是插值搜索，只有极少数程序员知道它，而每个人都知道二分查找。我认为，在有序列表中快速查找是一种非常有用和基本的算法，这几乎没什么疑问。

两者的实现方式几乎相同 - 所以这不是问题。

它在均匀分布的数据上执行O(log(log(n)))，而二分查找的执行时间是O(log(n))。这意味着搜索40亿个数字仅需要5个探测，而不是32个，效果要好得多！

即使是在非完美均匀数据上，它大部分情况下的表现仍然非常好。只有当数据非常倾斜时，它才像二分查找那样糟糕甚至更糟。在数据高度倾斜的情况下，它的最坏情况是O(n)，但这在大多数实际情况下都比较少见。

即便如此，人们仍然可以构造一个奇偶算法来在两种算法之间交替使用，并获得二分查找的最坏情况和插值查找的平均情况以缓解极端情况。

真的没有很好的理由让大多数程序员/库对其视而不见。

还有其他能够超越这个算法吗？

- Chris Harris

---

听起来像是一个喜欢引发争端的人；在我看来不是一个真正的问题。 - Mitch Wheat

建议：社区模式，就像其他“Foo的隐藏功能”，“史上最佳Bar”等问题一样。 - VolkerK

“5个探针对32个探针，用于40亿条目”听起来可能是一个巨大的改进，但这就像是“我有一个算法只需要1e-7秒，而下一个最好的算法需要整整1e-5秒，使我的算法快了100倍”。这两个绝对数字之间几乎没有什么区别。这种程度的改进只有在'n'接近真正巨大的数字时才变得相关。 - paxdiablo

已投票重新开放。这个问题应该很快就会被解决，但可能不会得到太多关注。 - Cerebrus

重新开放（但我仍然犹豫不决 - 你得到了利益的怀疑）。祝你回答顺利。 - paxdiablo

Answer 1

我提名Smoothsort。它是一种原地排序算法，最坏情况下时间复杂度为O(n log n)，最好情况下为O(n)。

- Stewart

---

不错的提名！我之前也没听说过这个 - 它确实可以解决堆排序中的一个主要问题。我认为归并排序通常比堆排序更可取，因为它在排序时更好地利用了局部性。我做了一些检查，并发现对于它是否在实践中更好的结果是交织的，你看过这篇论文讨论它的性能特点吗？我找不到其他的了。http://iwi.eldoc.ub.rug.nl/FILES/root/1991/InfProcLettBron/1991InfProcLettBron.pdf - Chris Harris

Answer 2

Trie/三叉树 ... 快速前缀匹配！我肯定比堆或显式链接列表结构使用它们更多（尽管带有“next”的隐式链接列表通常很有用）。

- Robert Fraser

---

整个trie领域受到了很大的忽视。早期的、朴素的trie对内存的需求很高，而且速度也不是很快，但是近年来进行了一些出色的工作；例如Judy树、burst树、fusion树等等。它们现在已经成为任何类型的二叉树甚至哈希表在某些情况下的严肃竞争对手。 - Tom Anderson

Answer 3

对于smoothsort的提名，我也赞同。它在理论上非常美丽，并且渐近地达到了最佳状态。

如果你好奇，我在我的个人网站上写了一篇关于这种排序方法的解释，讲述了它的工作原理和来源。

另外，我完全同意插值查找算法也很棒。我很高兴看到还有其他人听说过它。 :-)

- templatetypedef