6

タイトルの大きな言葉を誤用していた場合はご容赦ください。私はそれらについてあまり詳しくありませんが、彼らが私の問題を説明してくれることを願っています. これらの要件に従って文字列を試してエンコードするための精巧なスキームを作成しました。長さが 10^4 以上の文字列の場合、私が書いたコードは非常に遅く、疑問に思っています。一度に 200 個のチャンクを処理するためです (ただし、次のチャンクを取得するために 1 文字だけ前方に移動することがあります)。結果をより速く、またはより直線的に出力するように変更する必要があります (たとえば、処理された 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
4

1 に答える 1

6

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

出力内の各項目が、深くネストされた一連の括弧から外側に向かってどのように機能する必要があるかがわかりますか? これにより、すべての出力を取得するために、入力のサイズで 2 次時間がかかります。また、最初のいくつかの項目がゆっくりと生成され、リストの最後に到達するにつれてますます速くなるという動作も見られます。この削減はそれを説明しています。

ここでの主なパフォーマンスの問題は、新しい要素をリストの最後に追加することです。これには、追加するリストのサイズに比例して時間がかかります。より良い方法は、一定時間の操作であるフロントで cons を使用することです。これにより、出力が逆になるため、結果を逆にする必要があります。

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)時間がかかり、私たちがしていることとは何の関係もありません (すべての要素に 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 で末尾再帰がどのように機能するかについての直感が得られることを願っています。あなたの例では、末尾の再帰を削除し、 final に似た単純なスタイルで書き直すことをおgo勧めします。この投稿から提案した直感を使用して、「できるだけ早く、入力のできるだけ大きな接頭辞」を生成することを願っています (計算のためにさらに作業が必要な場合でも、x:xsすぐに yieldを返すことに注意してください。これは (非) アクションの怠惰です)。xxs

于 2013-06-03T17:53:51.223 に答える