6

私は岡崎の Purely Functional Data Structures を独学しており、現在演習 3.4に取り組んでおり、重みに偏った左翼ヒープについて推論し、実装するよう求めています。これは私の基本的な実装です:

(* 3.4 (b) *)
functor WeightBiasedLeftistHeap (Element : Ordered) : Heap =
struct
  structure Elem = Element

  datatype Heap = E | T of int * Elem.T * Heap * Heap

  fun size E = 0
    | size (T (s, _, _, _)) = s
  fun makeT (x, a, b) =
    let
      val sizet = size a + size b + 1
    in
      if size a >= size b then T (sizet, x, a, b)
      else T (sizet, x, b, a)
    end

  val empty = E
  fun isEmpty E = true | isEmpty _ = false

  fun merge (h, E) = h
    | merge (E, h) = h
    | merge (h1 as T (_, x, a1, b1), h2 as T (_, y, a2, b2)) =
      if Elem.leq (x, y) then makeT (x, a1, merge (b1, h2))
      else makeT (y, a2, merge (h1, b2))
  fun insert (x, h) = merge (T (1, x, E, E), h)

  fun findMin E = raise Empty
    | findMin (T (_, x, a, b)) = x
  fun deleteMin E = raise Empty
    | deleteMin (T (_, x, a, b)) = merge (a, b)
end

ここで、3.4 (c) & (d) で、次のように尋ねます。

現在、mergeは 2 つのパスで動作します。 への呼び出しで構成されるトップダウン パスmergeと、ヘルパー関数 への呼び出しで構成されるボトムアップ パスmakeTです。merge単一のトップダウン パスで動作するように変更します。mergeのトップダウン バージョンには、怠惰な環境でどのような利点がありますか? 並行環境では？

mergeインライン化するだけで関数を変更しましたmakeTが、利点が見られないため、演習のこれらの部分の精神を把握していないと思います。私は何が欠けていますか？

  fun merge (h, E) = h
    | merge (E, h) = h
    | merge (h1 as T (s1, x, a1, b1), h2 as T (s2, y, a2, b2)) =
      let
        val st = s1 + s2
        val (v, a, b) =
          if Elem.leq (x, y) then (x, a1, merge (b1, h2))
          else (y, a2, merge (h1, b2))
        in
          if size a >= size b then T (st, v, a, b)
          else T (st, v, b, a)
        end

遅延評価に関して、1 つのポイントを把握できたと思います。サイズの計算に再帰マージを使用しない場合、子が必要になるまで再帰呼び出しを評価する必要はありません。

  fun merge (h, E) = h
    | merge (E, h) = h
    | merge (h1 as T (s1, x, a1, b1), h2 as T (s2, y, a2, b2)) =
      let
    val st = s1 + s2
        val (v, ma, mb1, mb2) =
        if Elem.leq (x, y) then (x, a1, b1, h2)
        else (y, a2, h1, b2)
      in
        if size ma >= size mb1 + size mb2
        then T (st, v, ma, merge (mb1, mb2))
        else T (st, v, merge (mb1, mb2), ma)
      end

それだけですか？ただし、同時実行性についてはわかりません。

4

2 に答える 2

1

怠惰な環境では、WMERGE-3-4C 機能には何のメリットもありません。元のダウンアップマージが行ったすべての作業を引き続き実行します。言語システムが記憶するのは簡単ではないことは確かです..並行環境でのWMERGE-3-4C関数には何のメリットもありません。WMERGE-3-4C への各呼び出しは、すべての作業を行ってから、バックを WMERGE-3-4C の別のインスタンスに渡します。実際、手動で再帰を排除した場合、WMERGE-3-4C は、スタックを蓄積しながらすべての作業を行う単一のループとして実装でき、次にスタックで REDUCE 作業を行う 2 番目のループとして実装できます。最初のループは自然に並列化できるわけではありませんが、リストに要素が 1 つだけ残るまで、ペアで関数を並列に呼び出すことによって、REDUCE が動作する可能性があります。

于 2010-12-07T11:26:33.277 に答える
1

遅延評価に関する限り、基本的には理解していると思います。マージを行うたびに何かを見つけるためにデータ構造全体をたどらなければならない場合、遅延評価を使用することはあまり役に立ちません。 ..

同時実行性に関しては、あるスレッドがマージを評価しているときに、別のスレッドが来て何かを調べたい場合、少なくとも最初のスレッドがマージを完了するまで、有用なことは何もできないという問題があると思います. （それ以上かかることもあります。）

于 2010-12-03T00:30:44.800 に答える