Haskellの線形時間オンラインアルゴリズム

Question

私はタイトルに大きな言葉を誤用した場合ご容赦ください。私はあまり知識がありませんが、私の問題を説明してくれることを願っています。私は、theseの要件に従って文字列を試してエンコードするための手の込んだ仕組みを書いていました。長さ10^4以上の文字列の場合、私が書いたコードは非常に遅いです、と私は思ったんだけど - それは（次のチャンクを取るために、時々、前方のみ1文字を移動するが）一度に200のチャンクを処理するので、可能性があり、それは、結果をより速くまたはより線形に出力するように修正することができる（例えば、処理された200文字ごとに結果を即座に出力する）。そのような目立つ最適化の助けを借りていただければ幸いです。 TELの提案パー

、私は私の例を簡略化し：

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 

出力の各アイテムが、深くネストされたかっこのシリーズから外側に向かってどのように働く必要があるかを参照してください。これにより、すべての出力を得るために、入力のサイズで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)時間を要し、私たちがやっていることとは何の関係もありません（逆に、各要素に1つを加えて順序を保つことと何が関係していますか？

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を返すことは、xsを計算するために何らかの作業が必要であっても、すぐにxを返すことに注意してください。これは（非）アクションでの怠惰です）。