data-structures - 权重偏左的堆 : advantages of top-down version of merge?

Question

我正在自学Okasaki's Purely Functional Data Structures, now on exercise 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) 中，它要求:

Currently, merge operates in two passes: a top-down pass consisting of calls to merge, and a bottom-up pass consisting of calls to the helper function, makeT. Modify merge to operate in a single, top-down pass. What advantages would the top-down version of merge have in a lazy environment? In a concurrent environment?

我通过简单地内联makeT来更改merge函数，但我没有看到任何优点，所以我认为我还没有掌握这些部分的精神锻炼。我错过了什么？

  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

就这些了吗？不过我不确定并发性。

Answer 1

我认为您基本上已经了解了惰性求值——如果您每次都必须遍历整个数据结构来找出任何内容，那么使用惰性求值并不是很有帮助合并...

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