46

情景

我有几个数字范围。这些范围不重叠——因为它们不重叠，所以逻辑上的结果是任何时候都不能有一个数字属于多个范围。每个范围是连续的（单个范围内没有空洞，因此范围 8 到 16 将真正包含 8 到 16 之间的所有数字），但两个范围之间可以有空洞（例如范围从 64 开始到 128，下一个范围从 256 开始到 384），因此某些数字可能根本不属于任何范围（在此示例中，数字 129 到 255 不属于任何范围）。

问题

我得到一个数字，需要知道该数字属于哪个范围......如果它属于任何范围。否则我需要知道它不属于任何范围。速度当然很重要；我不能简单地检查 O(n) 的所有范围，因为可能有数千个范围。

简单的解决方案

一个简单的解决方案是将所有数字保存在一个排序的数组中并对其运行二进制搜索。那至少会给我 O(log n)。当然，二进制搜索必须进行一些修改，因为它必须始终检查范围的最小和最大数字。如果要查找的数字介于两者之间，则我们找到了正确的范围，否则我们必须搜索低于或高于当前值的范围。如果最后只剩下一个范围并且数字不在该范围内，则该数字根本不在范围内，我们可以返回“未找到”结果。

范围也可以以某种树结构链接在一起。这基本上就像一个带有二进制搜索的排序列表。优点是修改树比排序数组（添加/删除范围）更快，但不像我们浪费一些额外的时间来保持树的平衡，随着时间的推移，树可能会变得非常不平衡，这将导致搜索比对排序数组的二分搜索慢得多。

可以争论哪种解决方案更好或更差，因为在实践中搜索和修改操作的数量几乎是平衡的（每秒执行的搜索和添加/删除操作数量相同）。

问题

对于这类问题，是否有比排序列表或树更好的数据结构？也许在最好的情况下甚至比 O(log n) 更好，在最坏的情况下可能比 O(log n) 更好？

以下是可能对这里有所帮助的一些附加信息： 所有范围始终以 2 的幂的倍数开始和结束。它们总是以相同的 2 次幂开始和结束（例如，它们都以 4 的倍数或 8 的倍数或 16 的倍数等开始/结束）。两个的幂在运行期间不能改变。在添加第一个范围之前，必须设置 2 的幂，并且所有添加的范围必须以该值的倍数开始/结束，直到应用程序终止。我认为这可以用于优化，好像它们都以例如 8 的倍数开始，我可以忽略所有比较操作的前 3 位，如果有的话，其他位会告诉我范围。

我阅读了有关部分和范围树的信息。这些是问题的最佳解决方案吗？有没有可能更好的解决方案？这个问题听起来类似于 malloc 实现必须做的事情（例如，每个释放的内存块都属于一个可用内存范围，而 malloc 实现必须找出哪一个），那么这些通常如何解决问题？

4

5 回答 5

25

在运行了各种基准测试后，我得出结论，只有树状结构才能在这里工作。排序列表当然显示了良好的查找性能 - O(log n) - 但它显示了可怕的更新性能（与树相比，插入和删除的速度要慢 10 倍以上！）。

平衡二叉树也具有 O(log n) 查找性能，但是更新速度要快得多，也在 O(log n) 左右，而排序列表更像 O(n) 用于更新 (O(log n) 到找到插入的位置或要删除的元素，但是最多必须在列表中移动 n 个元素，这是 O(n))。

我实现了一个 AVL 树、一个红黑树、一个 Treap、一个 AA 树和 B 树的各种变体（B 在这里表示拜耳树，而不是二叉树）。结果：拜耳树几乎从未获胜。它们的查找很好，但它们的更新性能很差（因为在 B-Tree 的每个节点中，您又拥有一个排序列表！）。拜耳树仅在读取/写入节点是非常慢的操作的情况下（例如，当节点直接从硬盘读取或写入硬盘时）更胜一筹 - 因为 B-Tree 必须读取/写入的节点比任何其他节点少得多树，所以在这种情况下它会赢。但是，如果我们将这棵树留在记忆中，那么它就没有机会对抗其他树，对所有 B-Tree 粉丝感到抱歉。

Treap 最容易实现（少于其他平衡树所需代码行的一半，仅是不平衡树所需代码的两倍），并且在查找和更新方面表现出良好的平均性能......但我们可以做得更好那。

AA-Tree 显示出惊人的良好查找性能——我不知道为什么。他们有时会击败所有其他树（不是到目前为止，但仍然足以不巧合）......并且移除性能还可以，但是除非我太愚蠢而无法正确实现它们，否则插入性能真的很差（它执行每个插入的树旋转比任何其他树都多 - 即使是 B-Tree 也具有更快的插入性能）。

这给我们留下了两个经典，AVL 和 RB-Tree。它们都非常相似，但经过数小时的基准测试，有一点很清楚：AVL 树肯定比 RB-Tree 具有更好的查找性能。差异并不大，但在所有基准测试中，他们将赢得 2/3 的查找测试。不足为奇，毕竟 AVL 树比 RB-Tree 更严格地平衡，因此在大多数情况下它们更接近最优二叉树。我们在这里谈论的不是巨大的差异，它总是一场势均力敌的比赛。

另一方面，RB Trees 在几乎所有的测试运行中都击败了 AVL Trees，这并不是一场势均力敌的比赛。和以前一样，这是意料之中的。与 AVL 树相比，不那么严格平衡的 RB 树在插入时执行的树旋转要少得多。

删除节点怎么样？这里似乎很大程度上取决于节点的数量。对于小节点数（小于 50 万）RB 树再次拥有 AVL 树；差异甚至比插入更大。相当出乎意料的是，一旦节点数量增长到超过一百万个节点，AVL 树似乎就会赶上，并且与 RB 树的差异会缩小，直到它们或多或少同样快。不过，这可能是系统的影响。它可能与进程的内存使用或 CPU 缓存等有关。对 RB 树的负面影响比对 AVL 树的负面影响更大，因此 AVL 树可以赶上。对于查找（无论有多少节点，AVL 通常更快）和插入（无论有多少节点，RB 通常更快）没有观察到相同的效果。

结论：
我认为我能得到的最快速度是使用 RB-Trees，因为查找的次数只会比插入和删除的次数多一些，而且无论 AVL 在查找时有多快，整体性能都会受到它们的影响。更差的插入/删除性能。

也就是说，除非这里有人可能想出一个更好的数据结构来拥有大量的 RB 树 ;-)

于 2009-08-11T13:50:34.257 回答
9

创建一个排序列表并按下边距/开始排序。除非您拥有数百万个范围（甚至可能如此），否则这是最容易实现且速度足够快的方法。

查找范围时，请找到 所在的范围start <= position。由于列表已排序，因此您可以在此处使用二进制搜索。如果 ，该数字在范围内position <= end。

由于保证任何范围的结束都小于下一个范围的开始，因此在找到可能包含该位置的范围之前，您无需关心结束。

当你得到交叉点或者你有很多范围并且当你构建一个结构并经常查询时，所有其他数据结构都会变得有趣。

于 2009-07-28T11:34:27.813 回答
8

一个平衡的、在每个节点上都有范围的排序树似乎是答案。我无法证明它是最佳的，但如果我是你，我不会再看下去了。

于 2009-07-28T11:37:34.750 回答
2

如果数字的总范围很小，并且您有足够的内存，则可以创建一个包含所有数字的巨大表格。

例如，如果您有一百万个数字，您可以创建一个引用范围对象的表。

于 2014-01-14T15:37:42.900 回答
1

作为 O(log n) 平衡二叉搜索树 (BST) 的替代方案，您可以考虑构建按位（压缩）树。即您存储的数字位上的前缀树。

这为您提供了 O(w) 搜索、插入和删除性能；其中 w = 位数（例如 32 或 64 减去您的范围所基于的 2 的任何幂）。

并不是说它的性能会更好或更差，但它似乎是一个真正的替代方案，因为它与 BST 不同，但仍然具有良好的理论性能，并且允许像 BST 一样的前驱查询。

于 2015-01-28T18:30:43.823 回答