16

私はこれについてよく疑問に思っていましたが、満足のいく答えは見つかりませんでした。

なぜ(++)「高価」なのですか？遅延評価では、次のような式は評価しません。

xs ++ ys

必要になる前に、また必要なときに必要な部分だけを評価します。

誰かが私が欠けているものを説明できますか?

4

3 に答える 3

15

結果のリスト全体にアクセスする場合、遅延評価は計算を保存しません。特定の各要素が必要になるまで遅延するだけですが、最後に同じことを計算する必要があります。

連結リストをトラバースする場合xs ++ ys、最初の部分（xs）の各要素にアクセスすると、少し一定のオーバーヘッドが追加され、xs使用されたかどうかがチェックされます。

したがって、++左または右に関連付けると、大きな違いが生じます。

  • 次のようnに長さkのリストを左側に関連付ける(..(xs1 ++ xs2) ... ) ++ xsnと、最初のk要素のそれぞれO(n)にアクセスするのに時間がかかり、次の要素のそれぞれにアクセスするのに時間kがかかりますO(n-1)。したがって、リスト全体をトラバースするには時間がかかりO(k n^2)ます。あなたはそれをチェックすることができます

    sum $ foldl (++) [] (replicate 100000 [1])

    本当に時間がかかります。

  • のようnに長さkのリストを右側に関連付けるxs1 ++ ( ..(xsn_1 ++ xsn) .. )と、各要素に対して一定のオーバーヘッドしか得られないため、リスト全体をトラバースするのは。だけになりO(k n)ます。あなたはそれをチェックすることができます

    sum $ foldr (++) [] (replicate 100000 [1])

    かなり合理的です。

編集：これは背後に隠された魔法ShowSです。各文字列xsを showString xs :: String -> String（showStringの単なるエイリアス(++)）に変換してこれらの関数を構成すると、それらの構成をどのように関連付けても、最終的には右から左に適用されます。線形時間計算量を取得するために必要なものです。（これは単にであるため(f . g) xですf (g x)。）

両方を確認できます

length $ (foldl (.) id (replicate 1000000 (showString "x"))) ""

と

length $ (foldr (.) id (replicate 1000000 (showString "x"))) ""

妥当な時間で実行します（foldr右から関数を作成するときのオーバーヘッドが少ないため、少し高速ですが、どちらも要素数が線形です）。

于 2012-09-06T09:40:48.600 に答える
5

++それ自体はそれほど高価ではありません。左から右にたくさんの組み合わせを開始すると問題が発生します。そのようなチェーンは次のように評価されます

  ( ([1,2] ++ [3,4]) ++ [5,6] ) ++ [7,8]
≡ let a = ([1,2] ++ [3,4]) ++ [5,6]
        ≡ let b = [1,2] ++ [3,4]
                ≡ let c = [1,2]
                  in  head c : tail c ++ [3,4]
                    ≡ 1 : [2] ++ [3,4]
                    ≡ 1 : 2 : [] ++ [3,4]
                    ≡ 1 : 2 : [3,4]
                    ≡ [1,2,3,4]
          in  head b : tail b ++ [5,6]
            ≡ 1 : [2,3,4] ++ [5,6]
            ≡ 1:2 : [3,4] ++ [5,6]
            ≡ 1:2:3 : [4] ++ [5,6]
            ≡ 1:2:3:4 : [] ++ [5,6]
            ≡ 1:2:3:4:[5,6]
            ≡ [1,2,3,4,5,6]
  in head a : tail a ++ [7,8]
   ≡ 1 : [2,3,4,5,6] ++ [7,8]
   ≡ 1:2 : [3,4,5,6] ++ [7,8]
   ≡ 1:2:3 : [4,5,6] ++ [7,8]
   ≡ 1:2:3:4 : [5,6] ++ [7,8]
   ≡ 1:2:3:4:5 : [6] ++ [7,8]
   ≡ 1:2:3:4:5:6 : [] ++ [7,8]
   ≡ 1:2:3:4:5:6 : [7,8]
   ≡ [1,2,3,4,5,6,7,8]

二次的な複雑さがはっきりとわかります。n番目の要素までしか評価したくない場合でも、これらすべての sを掘り下げる必要がありますlet。そのため、++is infixr、 for[1,2] ++ ( [3,4] ++ ([5,6] ++ [7,8]) )は実際にははるかに効率的です。しかし、単純なシリアライザなどを設計する際に注意を怠ると、上記のようなチェーンになってしまう可能性があります。これが、初心者が警告される主な理由です++。

それはさておき、リンクされたリストをトラバースすることで機能するという単純な理由で、Prelude.++たとえば操作に比べて遅いです。これは、常にキャッシュの使用が最適化されていないなどですが、それほど問題ではありません。Bytestringこれにより、C のようなパフォーマンスを達成することはできなくなりますが、単純なリストのみを使用して適切に作成されたプログラムは、++Python などで作成された同様のプログラムに簡単に匹敵することができます。

于 2012-09-06T09:49:08.900 に答える
2

Petr の回答に 1 つか 2 つ追加したいと思います。

彼が指摘したように、最初にリストを繰り返し追加するのは非常に安価ですが、最後に追加するのはそうではありません。Haskell のリストを使用している限り、これは当てはまります。ただし、末尾に追加する必要がある特定の状況があります (たとえば、出力する文字列を構築している場合)。通常のリストでは、彼の答えで言及されている二次的な複雑さに対処する必要がありますが、これらの場合には、より良い解決策があります:差分リストです(トピックに関する私の質問も参照してください)。

簡単に言えば、リストを短いリストの連結ではなく、関数の合成として記述することで、関数を合成することで差分リストの先頭または末尾にリストまたは個々の要素を一定時間で追加できます。完了したら、通常のリストを線形時間 (要素数) で抽出できます。

于 2012-09-06T10:00:54.750 に答える