常数时间搜索

Question

常数时间搜索

5

假设我有一根棒子，我把它切成了若干段。给定原始棒子上的一个点，是否有一种方法可以在常数时间内找出它属于哪一段？

例如：

  |------------------|---------|---------------|
  0.0                4.5       7.8532          9.123

给定一个位置：

                                   ^
                                   |
                                   8.005

我想取得第三个元素。

使用二分查找可以在O(log n)的时间内轻松获得这样的答案，但是否有可能在预处理“截断”位置的情况下以O(1)的时间复杂度完成呢？

- Ecir Hana

2

这取决于所需的精度。在这个简单的例子中，使用4位小数精度，一个包含91230个元素的预填充段数组将在位置80050进行单次查找，以确定它命中哪个段。 - Joachim Isaksson

2

@JoachimIsaksson 我非常确定这不是他想要的... - No Idea For Name

@NoIdeaForName 这就是为什么这是一个好建议的原因;-) 即使它被证明是不切实际的，相同的技术也可以对其他问题有用。它很粗糙且占用空间，但非常有效。 - user395760

@JoachimIsaksson 我对float的精度很感兴趣。但还是谢谢你的建议！ - Ecir Hana

@EcirHana 最小的片段与整个杆相比有多小？从整个杆到最小浮点精度或最小/最大尺寸都可以。 - Joachim Isaksson

@JoachimIsaksson 很好的问题！我认为片段大小可能会有限制：0.01-100000.0（也许这甚至有点慷慨）。至于整个长度，我不太清楚——可能很长。 - Ecir Hana

4个回答

0

对于任意的切割和精度，你必须将位置与各种起始点或结束点进行比较。

但是，如果你只需要少量的切割，性能不应该成为问题。

例如，即使有十个段，你只需要进行九次比较，计算量并不大。

当然，你总是可以将情况转化为一个多项式公式（如ax^4 + bx^3 +cx^2 + dx + e），使用同时方程生成一个片段，但最高幂往往随着片段数而上升，因此并不像简单检查那样高效。

- paxdiablo

这听起来更像是关于算法的边界和效率的大学问题，而不是实际的编程问题。 - No Idea For Name

难道没有一种预处理位置或构建某些加速结构以使其更快的方法吗？ - Ecir Hana

@EcirHana，是的，请看我的方程式评论。但是，除非有很多段落，否则我不确定效率提高是否值得。 - paxdiablo

@paxdiablo 嗯，我不是很确定。如果有一个上限比如说2^16会有帮助吗？（另外参见：https://en.wikipedia.org/wiki/Quartic_function） - Ecir Hana

@EcirHana，使用2^16个段的平衡二叉树搜索可能是最好的方法，最多需要16次比较就能找到基于输入值的段。虽然这比O(1)查找解决方案慢，但(1)它是可行的；而且(2)你可能不会注意到。 - paxdiablo

显示剩余2条评论

0

您不可能使用基于比较的算法获得更好的效果，将正IEEE浮点数的31个非符号位重新解释为31位整数是一种保序变换，因此tries和van Emde Boas树都是可选的。我会首先向您推荐三层trie树。

- David Eisenstat

0

您可以为每个位置分配一个整数，并将其用作查找表的索引，这样可以获得常量时间的查找。如果您的木棒短而且不会切成毫米长的小片，那么这非常容易实现。如果您可以接受这种近似值，那就是我的建议之一。

还有一种更加高级的方法可以进一步推广。在查找表的每个元素中，存储中间位置以及左右两侧的段ID。这样进行一次查找（O(1)）和一次比较（O(1)）。缺点是查找表需要足够大，以至于同一个表元素的范围内从来没有超过两个不同的段。再次强调，这取决于您的要求和输入数据是否适用。

- Ulrich Eckhardt

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

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

- user2566092 · Accepted Answer

如果你假设你想查询的点是沿着杆均匀随机选择的，那么你可以有一个预期的恒定时间解决方案，而不需要疯狂的内存爆炸，如下所示。如果你将杆分成N个等距的部分，其中N是你的杆中原始不规则间隔的数量，然后记录每个N个等大小的部分与哪些原始不规则段重叠，那么要进行查询，你首先只需取查询点并进行简单的四舍五入，以找出它位于哪个等距离的部分，然后使用该索引查找哪个原始段与等距离的部分相交，然后检查每个相交的原始段以查看该段是否包含你的点（如果你想确保最坏情况下的性能仍然是对数级别，可以使用二分查找）。如果假设查询点是沿着你的杆随机选择的，则此方法的期望运行时间是恒定的，并且如果你的杆最初被切成N个不规则的部分，则内存量为O（N），因此没有疯狂的内存要求。

期望O(1)运行时间的证明：

当你计算原始N个不规则段和我建议构造的N个等距离部分之间的相交对的总数时，总数不会超过2*（N+1）（因为如果你将所有常规和不规则段的端点排序，则新的相交对始终可以归因于定义常规或不规则段的端点之一）。因此，你有一个最多包含2(N+1)个不规则段的多重集，在它们之间以某种方式分布在它们相交的N个常规段中。实际上，相交在常规段之间的分布并不重要。当你有一个均匀的查询点并计算与包含查询点的常规段相交的不规则段的期望数量时，每个常规段都有被查询点选择的概率为1/N，因此需要检查的相交的不规则段的期望数量为2*(N+1)/N=O(1)。