Haskell Linear-Time Online Algorithm

Question

Пожалуйста, простите меня, если я неправильно использовал большие слова в названии; Я не слишком осведомлен о них, но надеюсь, что они описывают мою проблему. Я написал сложную схему, чтобы попытаться кодировать строки в соответствии с требованиями these. Для строк длиной 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

Haskell и хвостовая рекурсия не ладят, а также другие функциональные языки и хвостовая рекурсия. Давайте немного ручным сокращением на каком-то очень простом коде, чтобы узнать, что происходит с хвостовой рекурсией. Вот хвостовая рекурсивная реализация 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 

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

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

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 требуется еще одна работа - это лень в (не) действии).