52

私は現在、オンラインでLearn you a Haskellの本を読み進めており、一部のリストの連結は非効率的である可能性があることを著者が説明している章に到達しました。たとえば、

((((a ++ b) ++ c) ++ d) ++ e) ++ f

おそらく非効率的です。著者が思いついた解決策は、次のように定義された「差分リスト」を使用することです。

newtype DiffList a = DiffList {getDiffList :: [a] -> [a] }

instance Monoid (DiffList a) where
    mempty = DiffList (\xs -> [] ++ xs)
    (DiffList f) `mappend` (DiffList g) = DiffList (\xs -> f (g xs))

DiffList場合によっては、単純な連結よりも計算効率が高い理由を理解するのに苦労しています。誰かが私に簡単な言葉で上記の例がそれほど非効率的である理由を説明できますか、そしてどのようにDiffListこの問題を解決しますか？

4

2 に答える 2

91

の問題

((((a ++ b) ++ c) ++ d) ++ e) ++ f

入れ子です。のアプリケーション(++)は左にネストされており、それは悪いことです。右入れ子

a ++ (b ++ (c ++ (d ++ (e ++f))))

問題にはなりません。これは、(++)が次のように定義されているためです。

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

したがって、使用する方程式を見つけるには、実装は式ツリーに飛び込む必要があります

             (++)
             /  \
          (++)   f
          /  \
       (++)   e
       /  \
    (++)   d
    /  \
 (++)   c
 /  \
a    b

左側のオペランドが空かどうかがわかるまで。空でない場合は、頭を上に向けてバブリングしますが、左のオペランドの末尾はそのままにしておくため、連結の次の要素が要求されると、同じ手順が再開されます。

連結が右にネストされている場合、の左のオペランド(++)は常に上部にあり、空のチェック/ヘッドのバブリングはO（1）です。

ただし、連結が左にネストされ、nレイヤーが深く、最初の要素に到達するn場合、結果の要素ごとに（最初のリストからn-1のもの、2番目のリストからのものなど）、ツリーのノードをトラバースする必要があります。

a = "hello"で考えてみましょう

hi = ((((a ++ b) ++ c) ++ d) ++ e) ++ f

そして、評価したいと思いtake 5 hiます。したがって、最初に、次のことを確認する必要があります

(((a ++ b) ++ c) ++ d) ++ e

空です。そのためには、

((a ++ b) ++ c) ++ d

空です。そのためには、

(a ++ b) ++ c

空です。そのためには、

a ++ b

空です。そのためには、

a

空です。ふぅ。そうではないので、組み立てて再び泡立てることができます

a ++ b                             = 'h':("ello" ++ b)
(a ++ b) ++ c                      = 'h':(("ello" ++ b) ++ c)
((a ++ b) ++ c) ++ d               = 'h':((("ello" ++ b) ++ c) ++ d)
(((a ++ b) ++ c) ++ d) ++ e        = 'h':(((("ello" ++ b) ++ c) ++ d) ++ e)
((((a ++ b) ++ c) ++ d) ++ e) ++ f = 'h':((((("ello" ++ b) ++ c) ++ d) ++ e) ++ f)

そして、のために'e'、私たちは繰り返さなければなりません、そして'l'sのためにも...

木の一部を描くと、泡立ちは次のようになります。

            (++)
            /  \
         (++)   c
         /  \
'h':"ello"   b

最初になります

     (++)
     /  \
   (:)   c
  /   \
'h'   (++)
      /  \
 "ello"   b

その後

      (:)
      / \
    'h' (++)
        /  \
     (++)   c
     /  \
"ello"   b

トップに戻るまで。最終的にトップレベルの右の子になるツリーの(:)構造は、左端のリストが空でない限り、元のツリーの構造とまったく同じです。

 (++)
 /  \
[]   b

ノードはちょうどに折りたたまれますb。

したがって、短いリストの左にネストされた連結がある場合、連結の先頭を取得することはO（ネストの深さ）操作であるため、連結は2次式になります。一般に、左ネストの連結

(...((a_d ++ a_{d-1}) ++ a_{d-2}) ...) ++ a_2) ++ a_1

O(sum [i * length a_i | i <- [1 .. d]])完全に評価することです。

差分リスト（説明を簡単にするためのニュータイプラッパーはありません）では、構成が左ネストされているかどうかは重要ではありません

((((a ++) . (b ++)) . (c ++)) . (d ++)) . (e ++)

または右ネスト。ネスティングを通過して、に到達する(a ++)と、それ(++)は式ツリーの一番上に持ち上げられます。したがって、の各要素に到達すると、a再びO（1）になります。

実際、最初の要素が必要になるとすぐに、構成全体が差分リストに再関連付けされます。

((((a ++) . (b ++)) . (c ++)) . (d ++)) . (e ++) $ f

になります

((((a ++) . (b ++)) . (c ++)) . (d ++)) $ (e ++) f
(((a ++) . (b ++)) . (c ++)) $ (d ++) ((e ++) f)
((a ++) . (b ++)) $ (c ++) ((d ++) ((e ++) f))
(a ++) $ (b ++) ((c ++) ((d ++) ((e ++) f)))
a ++ (b ++ (c ++ (d ++ (e ++ f))))

その後、各リストは、(++)前のリストが消費された後のトップレベルのすぐ左のオペランドになります。

その中で重要なことは、付加関数(a ++)が引数を検査せずに結果の生成を開始できることです。そのため、

             ($)
             / \
           (.)  f
           / \
         (.) (e ++)
         / \
       (.) (d ++)
       / \
     (.) (c ++)
     / \
(a ++) (b ++)

経由

           ($)---------
           /           \
         (.)           ($)
         / \           / \
       (.) (d ++) (e ++)  f
       / \
     (.) (c ++)
     / \
(a ++) (b ++)

に

     ($)
     / \
(a ++) ($)
       / \
  (b ++) ($)
         / \
    (c ++) ($)
           / \
      (d ++) ($)
             / \
        (e ++)  f

最終リストの構成された関数について何も知る必要がないfので、それは単なるO(depth)書き直しです。次にトップレベル

     ($)
     / \
(a ++)  stuff

になります

 (++)
 /  \
a    stuff

のすべての要素をa1つのステップで取得できます。この例では、純粋な左ネストがあり、1回の書き換えのみが必要です。その場所の関数が（たとえば）(d ++)左にネストされたコンポジションであった(((g ++) . (h ++)) . (i ++)) . (j ++)場合、、トップレベルの再関連付けはそれをそのままにし、($)以前のすべてのリストの後でトップレベルの左オペランドになると再関連付けされます消費されました。

すべての再関連付けに必要な合計作業量はO(number of lists)であるため、連結の全体的なコストはですO(number of lists + sum (map length lists))。（つまり、深く左にネストされたものをたくさん挿入することで、これにも悪いパフォーマンスをもたらす可能性があります([] ++)。）

The

newtype DiffList a = DiffList {getDiffList :: [a] -> [a] }

instance Monoid (DiffList a) where
    mempty = DiffList (\xs -> [] ++ xs)
    (DiffList f) `mappend` (DiffList g) = DiffList (\xs -> f (g xs))

抽象的に処理する方が便利なように、それをラップするだけです。

DiffList (a ++) `mappend` DiffList (b ++) ~> DiffList ((a ++) . (b++))

出力の生成を開始するために引数を検査する必要がない関数に対してのみ効率的であることに注意してください。任意の関数がDiffListsでラップされている場合、そのような効率の保証はありません。特に、（ラップされているかどうかに関係なく）追加すると、右ネストで構成された場合(++ a)の左ネストツリーが作成される可能性があるため、コンストラクターが公開されている場合は、それを使用して連結動作を作成できます。(++)O(n²)DiffList

于 2012-12-14T13:34:35.653 に答える
6

連結の定義を確認すると役立つ場合があります。

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

ご覧のとおり、2つのリストを連結するには、左側のリストに目を通し、その「コピー」を作成する必要があります。これにより、その終わりを変更できます（これは、古いリストの終わりを直接変更できないためです。リスト、不変性のため）。

正しい連想方法で連結を行う場合、問題はありません。一度挿入されると、リストに再度触れる必要はありません（++の定義が右側のリストを検査しないことに注意してください）。したがって、各リスト要素は、合計時間O（N）の間「1回」だけ挿入されます。

--This is O(n)
(a ++ (b ++ (c ++ (d ++ (e ++ f)))))

ただし、左結合の方法で連結を行う場合は、最後に別のリストフラグメントを追加するたびに、「現在の」リストを「破棄」して「再構築」する必要があります。各リスト要素は、次の場合に繰り返されます。それが挿入され、将来のフラグメントも追加されるたびに！これは、strcatを連続して複数回単純に呼び出す場合にCで発生する問題のようなものです。

差分リストに関しては、秘訣は、最後に明示的な「穴」を保持することです。DListを通常のリストに戻すときは、穴に入れたいものを渡すと、すぐに使用できるようになります。一方、通常のリストは常に最後の穴を塞ぐ[]ので、（連結するときに）変更する場合は、リストを開いてそのポイントに到達する必要があります。

関数を使用した差分リストの定義は、最初は威圧的に見えるかもしれませんが、実際には非常に単純です。それらをオブジェクト指向の観点から見ることができます。不透明なオブジェクトの「toList」メソッドは、最後に穴に挿入する必要のあるリストを受け取り、DLの内部プレフィックスと提供されたテールを返します。すべての変換が完了した後、最後に「穴」を塞ぐだけなので、効率的です。

于 2012-12-14T13:33:29.760 に答える