haskell: структура данных для хранения восходящих целых чисел с очень быстрым поиском

Question

(Этот вопрос относится к моему предыдущему вопросу , точнее к моему ответу на него.)

Я хочу хранить все кубы натуральных чисел в структуре и искать конкретные целые числа, чтобы увидеть, являются ли они идеальными кубами.

Например,

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

Это намного быстрее, чем вычисление корня куба, но имеет сложность O(n^(1/3)) (я прав?).

Я думаю, было бы лучше использовать более сложную структуру данных.

Например, в C я могу сохранить длину уже сгенерированного массива (не списка - для более быстрой индексации) и выполнить бинарный поиск. Это будет O(log n) с более низким коэффициентом, чем в другой ответ на , что вопрос. Проблема в том, что я не могу выразить это на Хаскеле (и не думаю, что должен).

Или я могу использовать хеш-функцию (например, mod). Но я думаю, что было бы намного больше памяти, чтобы иметь несколько списков (или список списков), и это не снизило бы сложность поиска (все еще O(n^(1/3))), только коэффициент.

Я думал о каком-то дереве, но без каких-либо умных идей (к сожалению, я никогда не изучал CS). Я думаю, тот факт, что все целые числа возрастают, сделает мое дерево плохо сбалансированным для поиска.

И я вполне уверен, что этот факт о возрастающих целых числах может быть большим преимуществом для поиска, но я не знаю, как правильно его использовать (см. Мое первое решение, которое я не могу выразить в Haskell).

Answer 1

Несколько комментариев:

• Если у вас конечное число кубов, поместите их в Data.IntSet. Поиск - логарифмическое время. Алгоритм основан на деревьях Патриции и работе Джилла и Окасаки.

• Если в отсортированном списке бесконечно много кубов, вы можете выполнить бинарный поиск. начните с индекса 1, и вы будете удваивать его логарифмически много раз, пока не получите что-то достаточно большое, затем логарифмически много больше шагов, чтобы найти целое число или исключить его. Но, к сожалению, со списками, каждый поиск пропорционален размеру индекса. И вы не можете создать бесконечный массив с постоянным поиском.

На этом фоне я предлагаю следующую структуру данных:

Сортированный список отсортированных массивов кубов. Массив в позиции i содержит exp(2,i) элементов.

Тогда у вас есть немного более сложная форма бинарного поиска. Я не достаточно проснулся, чтобы провести анализ на макушке головы, но я верю, что это приводит вас к O ((log n) ^ 2) худшему случаю.

Answer 2

Вы можете выполнить поиск Фибоначчи (или любой другой, который вам нравится) по ленивому бесконечному дереву:

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