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

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

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

Например,

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

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

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

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

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

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

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


lookup data-structures haskell
person Valentin Golev    schedule 12.05.2010    source источник

Ответы (2)


arrow_upward
4
arrow_downward

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

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

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

Исходя из этого, я предлагаю следующую структуру данных:

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

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

person Norman Ramsey    schedule 12.05.2010

arrow_upward
2
arrow_downward

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

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
person ony    schedule 12.05.2010