6

我正在自学冈崎的纯功能数据结构,现在在练习 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以两种方式运行:由对 的调用组成的自上而下的传递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

我想我已经弄清楚了关于惰性评估的一点。如果我不使用递归合并来计算大小,那么在需要孩子之前不需要评估递归调用:

  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 的第二个循环。第一个循环不会自然地并行化,尽管 REDUCE 可以通过成对地并行调用函数来操作,直到列表中只剩下一个元素。

于 2010-12-07T11:26:33.277 回答
1

我认为就惰性求值而言,您基本上已经掌握了它——如果您最终不得不遍历整个数据结构以在每次进行合并时找出任何东西,那么使用惰性求值并不是很有帮助。 ..

至于并发性,我预计问题是,如果在一个线程正在评估合并时,另一个线程出现并想要查找某些内容,那么至少在第一个线程完成合并之前,它将无法完成任何有用的事情. (甚至可能需要更长的时间。)

于 2010-12-03T00:30:44.800 回答