haskell:一种数据结构,用于存储具有非常快速查找的升序整数。

几点意见:

• 如果你有有限的立方体,把它们放进去 Data.IntSet . 查找是对数时间。该算法是基于帕特里夏树和一篇论文吉尔和冈崎。

• 如果排序列表中有无限多的多维数据集,则可以执行二进制搜索。从索引1开始,您将对数加倍多次,直到得到足够大的值,然后再对数多次,以找到整数或将其排除。但不幸的是,对于列表,每次查找都与索引的大小成比例。你不能创造无限 数组 使用持续时间查找。

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

多维数据集排序数组的排序列表。位置上的阵列 i 包含 exp(2,i) 元素。

然后是稍微复杂一点的二进制搜索形式。 我还没有清醒到可以从头开始分析,但我相信这会让你陷入最坏的情况。

您可以在懒惰的无限树上执行斐波那契搜索(或任何其他您喜欢的搜索):

data Tree a = Empty
            | Leaf a
            | Node a (Tree a) (Tree a)

rollout Empty = []
rollout (Leaf a) = [a]
rollout (Node x a b) = rollout a ++ x : rollout b

cubes = backbone 1 2 where
    backbone a b = Node (b*b*b) (sub a b) (backbone (b+1) (a+b))

    sub a b | (a+1) == b = Leaf (a*a*a)
    sub a b | a == b = Empty
    sub a b = subBackbone a (a+1) b

    subBackbone a b c | b >= c = sub a c
    subBackbone a b c = Node (b*b*b) (sub a b) (subBackbone (b+1) (a+b) c)

is_cube n = go cubes where
    go Empty = False
    go (Leaf x) = (x == n)
    go (Node x a b) = case (compare n x) of
                          EQ -> True
                          LT -> go a
                          GT -> go b