Haskell algorytm liniowy online

Question

Proszę mi wybaczyć, jeśli nadużyłem wielkich słów w tytule; Nie mam zbyt dużej wiedzy na ich temat, ale mam nadzieję, że opisują mój problem. Napisałem skomplikowany schemat próbowania kodowania ciągów zgodnie z wymaganiami these. W przypadku ciągów o długości 10^4 i wyższych, napisany przeze mnie kod jest dość powolny i zastanawiam się - skoro przetwarza 200 kawałków na raz (choć przesuwa tylko jedną postać do przodu, by wziąć następny fragment), czy mógłby być zmodyfikowane tak, aby wynik był szybszy lub bardziej liniowy (np. natychmiast wyświetlaj wynik dla każdego 200 znaków). Przydałaby się jakakolwiek pomoc w tej lub innych zauważalnych optymalizacjach.

Za sugestią TEL, w I uproszczone mojego przykładu:

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 i ogon rekurencji nie dogadać, jak również inne języki funkcjonalne i ogon rekurencji. Zróbmy ręczną redukcję na bardzo prostym kodzie, aby zobaczyć, co się dzieje z rekurencją ogona. Oto rekursywna rekurencyjna implementacja map (1+).

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

Również musimy pamiętać definicję (++):

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

Teraz zmniejszyć go [1,2,3,4,5] []. Należy pamiętać, że [x,y,z] jest notacją dla x:(y:(z:[])) lub dla skrótu 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 

Zobacz, jak każdy element w wyjściu musi działać na zewnątrz z głęboko zagnieżdżonej serii nawiasów? Powoduje to, że zajmuje on kwadratowy czas w rozmiarze wejścia, aby uzyskać wszystkie dane wyjściowe. Zobaczysz także zachowanie, które powoduje, że kilka pierwszych pozycji ustępuje powoli, a gdy dojdziesz do końca listy, staje się coraz szybsze. Ta redukcja wyjaśnia to.

Głównym problemem z wydajnością jest tutaj dodanie nowego elementu na końcu listy, co zajmuje czas proporcjonalny do rozmiaru listy, do której dodajesz. Lepszym sposobem jest przeciwdziałanie z przodu, co jest procesem czasowym. Spowoduje to, że wyjście wyjdzie odwrotnie, więc musisz odwrócić wynik.

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) 

I niech zmniejszają:

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! 

Więc to wyraźnie mniej pracy niż w pierwszej wersji. Jest to styl używany w ścisłych językach, takich jak Scheme i ML, ponieważ ma on dobrą wydajność pamięci. Ma jednak pewne wady:

• Wszystkie dane wejściowe muszą zostać zużyte przed wyprodukowaniem dowolnego wyjścia. Rzeczywiście, całe obliczenia są wykonywane zanim jakiekolwiek wyniki zostaną uzyskane.
• Z tego powodu nigdy nie daje żadnych danych wyjściowych po podaniu nieskończonej listy.
• Dotyczy to reverse, która zajmuje dodatkowy czas w postaci O(n) i nie ma nic wspólnego z tym, co robimy (co oznacza cofanie w związku z dodawaniem do każdego elementu i zachowaniem porządku?).

W leniwym języku, takim jak Haskell, możemy zrobić lepiej. Dziwnie i pięknie, sposób, w jaki robimy, to pisząc to jeszcze bardziej naiwnie.

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

i zmniejszają:

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 

To trwa nawet mniej pracy, a to zaczyna uzyskując wyjście zanim nawet patrząc na pozostałą część listy, a więc ma dobrą wydajność w obliczeniach strumienia i działa na nieskończone wejścia. Implementacja jest tak prosta i oczywista, jak można mieć nadzieję.

Mam nadzieję, że dzięki temu dowiesz się, jak działa rekursja ogona w Haskell. Na przykład sugeruję usunięcie rekursji i przepisywania ogona w stylu naiwnym, podobnym do naszego ostatecznego go, za pomocą intuicji, którą mam nadzieję zasugerowałem z tego postu, aby uzyskać "jak największy przedrostek wejścia, jak to możliwe, tak szybko jak to możliwe" (zauważ, że zwracanie x:xs natychmiast daje x, nawet jeśli jest jeszcze trochę pracy do zrobienia, aby obliczyć xs - to lenistwo w (nie) działaniu).