data-structures - haskell:一种用于存储升序整数且查找速度非常快的数据结构

Question

(这个问题与我的 previous question 相关，或者更确切地说与 my answer 相关。)

我想将自然数的所有立方体存储在一个结构中，并查找特定的整数以查看它们是否是完美的立方体。

例如，

cubes = map (\x -> x*x*x) [1..]
is_cube n = n == (head $ dropWhile (<n) cubes)

它比计算立方根快得多，但它的复杂度为O(n^(1/3))(我说得对吗？)。

我认为，使用更复杂的数据结构会更好。

例如，在 C 中，我可以存储已生成数组的长度(不是列表 - 为了更快的索引)并进行二分搜索。其系数将是 O(log n)，且系数低于 another answer对于这个问题。问题是，我无法用 Haskell 表达它(而且我认为我不应该)。

或者我可以使用哈希函数(如 mod)。但我认为拥有多个列表(或列表列表)会消耗更多内存，并且不会降低查找的复杂性(仍然O(n^(1/3)))，只有一个系数。

我想过一种树，但没有任何聪明的想法(遗憾的是我从未学过CS)。我认为，所有整数都升序的事实将使我的树在查找时不平衡。

我很确定关于升序整数的这一事实对于查找来说是一个很大的优势，但我不知道如何正确使用它(请参阅我的第一个解决方案，我无法在 Haskell 中表达)。

Answer 1

几条评论:

• 如果您有有限多个多维数据集，请将它们放入 Data.IntSet 中。查找时间是对数。算法基于 Patricia 树以及 Gill 和 Okasaki 的论文。

• 如果排序列表中有无限多个立方体，则可以进行二分搜索。从索引 1 开始，将其对数加倍多次，直到得到足够大的值，然后以对数更多的步骤来找到整数或将其排除。但不幸的是，对于列表，每次查找都与索引的大小成正比。而且您无法通过恒定时间查找创建无限数组。

在此背景下，我提出以下数据结构:

A sorted list of sorted arrays of cubes. The array at position i contains exp(2,i) elements.

然后你就有了稍微复杂一点的二分搜索形式。我还不够清醒，无法立即进行分析，但我相信这会让您遇到 O((log n)^2) 最坏的情况。