Хаскелл Линейное Время Онлайн Алгоритм

Question

Пожалуйста, прости меня, если я неправильно использовал громкие слова в названии; Я не слишком осведомлен о них, но надеюсь, что они описывают мою проблему. Я написал сложную схему, чтобы попытаться кодировать строки в соответствии с этими требованиями. Для строк длиной 10^4 и выше код, который я написал, довольно медленный, и я удивляюсь - поскольку он обрабатывает порции по 200 за раз (хотя иногда и перемещает только один символ вперед, чтобы взять следующий фрагмент), мог бы он быть изменен, чтобы выводить результат быстрее или более линейно (например, немедленно выводить результат для каждых 200 обработанных символов). Любая помощь с той или иной заметной оптимизацией будет принята с благодарностью.

По предложению Тела я упростил свой пример:

encode xs = encode' xs [] where
  encode' []     result = result
  encode' (z:zs) result
    | null test = encode' zs (result ++ [z])
    | otherwise = encode' (drop numZsProcessed zs) (result ++ processed)
   where test = ..some test
         toProcess = take 200 (z:zs)
         processed = ..do something complicated with toProcess
         numZsProcessed = ..number of z's processed

Answer 1

Хаскелл и хвостовая рекурсия не уживаются так же хорошо, как другие функциональные языки и хвостовая рекурсия. Давайте сделаем некоторое ручное сокращение для очень простого кода, чтобы увидеть, что происходит с хвостовой рекурсией. Вот хвост-рекурсивная реализация map (1+),

go [] r = r
go (x:xs) r = go xs (r ++ [1+x])

Также мы должны иметь в виду определение (++):

[] ++ ys = ys
(x:xs) ++ ys = x : (xs ++ ys)

Теперь давайте уменьшим go [1,2,3,4,5] [], Имейте в виду, что [x,y,z] это обозначение для x:(y:(z:[])) или для краткости x:y:z:[],

go [1,2,3,4,5] []
go [2,3,4,5] ([] ++ [2])   -- 2 here is actually the thunk 1+1, but
                           -- for compactness I am reducing earlier
go [3,4,5] (([] ++ [2]) ++ [3])
go [4,5] ((([] ++ [2]) ++ [3]) ++ [4])
go [5] (((([] ++ [2]) ++ [3]) ++ [4]) ++ [5])
go [] ((((([] ++ [2]) ++ [3]) ++ [4]) ++ [5]) ++ [6])
(((([] ++ [2]) ++ [3]) ++ [4]) ++ [5]) ++ [6]
((([2] ++ [3]) ++ [4]) ++ [5]) ++ [6]
(((2:([] ++ [3]) ++ [4]) ++ [5]) ++ [6]
((2:(([] ++ [3]) ++ [4]) ++ [5]) ++ [6]
(2:((([] ++ [3]) ++ [4]) ++ [5]) ++ [6]
2:(((([] ++ [3]) ++ [4]) ++ [5]) ++ [6])    -- first observable output
2:((([3] ++ [4]) ++ [5]) ++ [6])
2:((3:([] ++ [4]) ++ [5]) ++ [6])
2:(3:(([] ++ [4]) ++ [5]) ++ [6])
2:3:((([] ++ [4]) ++ [5]) ++ [6])           -- second observable output
2:3:(([4] ++ [5]) ++ [6])
2:3:(4:([] ++ [5]) ++ [6])
2:3:4:(([] ++ [5]) ++ [6])                  -- third observable output
2:3:4:([5] ++ [6])
2:3:4:5:([] ++ [6])                         -- fourth observable output
2:3:4:5:6:[]                                -- final output

Посмотрите, как каждый элемент в выходных данных должен выходить из глубоко вложенных серий скобок? Это заставляет его занимать квадратичное время в размере входных данных, чтобы получить весь вывод. Вы также увидите поведение, при котором первые несколько элементов выдаются медленно, и оно становится все быстрее и быстрее по мере достижения конца списка. Это сокращение объясняет это.

Основной проблемой производительности здесь является добавление нового элемента в конец списка, что занимает время, пропорциональное размеру списка, к которому вы добавляете. Лучший способ состоит в том, чтобы противостоять на фронте, который является постоянной операцией. Это приведет к обратному выводу, так что вам нужно поменять результат.

go [] r = reverse r
go (x:xs) r = go xs ((1+x):r)

reverse xs = rev xs []      -- roughly from the report prelude
rev [] r = r
rev (x:xs) r = rev xs (x:r)

И давайте уменьшим:

go [1,2,3,4,5] []
go [2,3,4,5] [2]
go [3,4,5] [3,2]
go [4,5] [4,3,2]
go [5] [5,4,3,2]
go [] [6,5,4,3,2]
reverse [6,5,4,3,2]
rev [6,5,4,3,2] []
rev [5,4,3,2] [6]
rev [4,3,2] [5,6]
rev [3,2] [4,5,6]
rev [2] [3,4,5,6]
rev [] [2,3,4,5,6]
[2,3,4,5,6]          -- first and all observable output!

Так что это явно меньше работы, чем первая версия. Этот стиль используется в строгих языках, таких как Scheme и ML, потому что он имеет хорошую производительность памяти. Однако у него есть некоторые недостатки:

• Все входные данные должны быть использованы до того, как будет получен какой-либо выход. Действительно, все вычисления выполняются до того, как будут получены какие-либо результаты.
• Из-за этого он никогда не выдает никаких результатов, если ему предоставляется бесконечный список.
• Это включает в себя reverse, который занимает дополнительное O(n) время и не имеет ничего общего с тем, что мы делаем (какое отношение имеет обращение к добавлению одного к каждому элементу и сохранению порядка?).

На ленивом языке, таком как Haskell, мы можем добиться большего. Странно и красиво, но мы пишем это еще более наивно.

go [] = []
go (x:xs) = (1+x):go xs

и уменьшить:

go [1,2,3,4,5]
2:(go [2,3,4,5])     -- first observable output
2:3:(go [3,4,5])     -- second observable output
2:3:4:(go [4,5])     -- third observable output
2:3:4:5:(go [6])     -- fourth observable output
2:3:4:5:6:(go [])    -- fifth observable output
2:3:4:5:6:[]         -- final output

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

Я надеюсь, что это даст вам некоторую интуицию о том, как работает хвостовая рекурсия в Haskell. Для вашего примера я предлагаю убрать хвостовую рекурсию и переписать в наивном стиле, похожем на наш финальный go Используя интуицию, я надеюсь, что из этого поста я предложил получить "как можно больший префикс ввода как можно скорее" (обратите внимание, что возвращение x:xs сразу дает x, даже если еще предстоит проделать определенную работу для вычисления xs - это лень в (не) действии.