하스켈 선형 시간 온라인 알고리즘

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

하스켈과 꼬리 재귀가 함께 얻을뿐만 아니라 다른 기능 언어와 꼬리 재귀하지 않습니다. 꼬리 재귀 (tail recursion)로 어떤 일이 벌어지고 있는지 알아보기 위해 몇 가지 간단한 코드를 수동으로 축소 해 보겠습니다. 여기에 map (1+)의 꼬리 재귀 구현이 있습니다.

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

은 이제 go [1,2,3,4,5] []을 줄일 수 있습니다 :

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

또한 우리는 마음에 (++)의 정의를 유지해야합니다. [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 

출력의 각 항목은 괄호의 중첩 시리즈에서 바깥쪽으로 그것의 방법을 작동해야하는 방법을 참조하십시오? 이렇게하면 모든 출력을 얻기 위해 입력 크기에서 2 차 시간이 걸립니다. 또한 처음 몇 가지 항목이 느리게 생성되는 동작을 볼 수 있으며 목록의 끝에 도달하면 빠르 고 빠릅니다. 이 감소는 그것을 설명합니다.

여기서 주요 성능 문제는 목록의 끝에 새 요소를 추가하는 것이므로 추가 할 목록의 크기에 비례하여 시간이 걸립니다. 더 좋은 방법은 앞쪽에 죄수를 두는 것인데, 죄수 잔업 시간입니다. 이렇게하면 출력이 반전되므로 결과를 반대로해야합니다.

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과 같은 엄격한 언어에서 사용되는 스타일입니다. 그러나 몇 가지 단점이 있습니다.

• 출력을 생성하려면 먼저 모든 입력을 사용해야합니다. 실제로 모든 계산은 결과가 생성되기 전에 수행됩니다.
• 무한한 목록이 주어지면 출력이 나오지 않습니다.
• 이것은 이며, 이는 O(n) 시간이 걸리고 우리가하는 일과 아무런 관련이 없습니다. (모든 요소에 하나를 추가하고 순서를 유지하는 것과 어떤 관계가 있습니까?)

하스켈과 같은 게으른 언어에서는 더 잘할 수 있습니다. 이상하고 아름답게, 우리가하는 일은 더 순진하게 그것을 쓰는 것입니다.

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 

그것은 더 적은 노력이 필요하고, 심지어는 목록의 나머지를보기 전에 출력을 산출 시작, 그래서 스트림 계산에 좋은 성능을 가지고에 작동 무한 입력. 그리고 구현은 당신이 바라는만큼 간단하고 명백합니다.

하스켈에서 꼬리 재귀가 작동하는 방식에 대해 직감을 줄 수 있기를 바랍니다. 예를 들어, 꼬리 재귀를 제거하고 우리의 최종 go과 비슷한 순진한 스타일로 다시 작성하는 것이 좋습니다. 직감을 사용하여이 게시물에서 "가능한 한 빨리 입력의 큰 접두사" (x:xs을 반환하면 xs을 계산하기 위해 수행해야 할 작업이 더 많이 있더라도 즉시 즉 x이 발생합니다 (즉, (비) 액션에서의 게으름).