重量级左派堆叠：自上而下的合并优势？ [英] Weight-Biased Leftist Heaps: advantages of top-down version of merge?

问题描述

我自我学习 Okasaki的纯功能数据结构，现在在练习3.4中，要求推理和实施一个偏重的左派堆。这是我的基本实现：

I am self-studying Okasaki's Purely Functional Data Structures, now on exercise 3.4, which asks to reason about and implement a weight-biased leftist heap. This is my basic implementation:

(* 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），它询问：

Now, in 3.4 (c) & (d), it asks:

目前，合并以两个
通过：由
调用$ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ b函数， makeT 。将合并修改为
，以单个自上而下的顺序操作。
从$ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $

在
的并发环境中？

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?

我更改了 merge 函数通过简单地内联 makeT ，但我没有看到任何优点，所以我想我没有把握这些练习的精神。我缺少什么？

I changed the merge function by simply inlining makeT, but I fail to see any advantages, so I think I haven't grasped the spirit of these parts of the exercise. What am I missing?

  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

---

我想我已经弄清楚了一点，懒惰的评价。如果我不使用递归合并来计算大小，那么在需要孩子之前，递归调用不需要进行评估：

---

I think I've figured out one point with regards to lazy evaluation. If I don't use the recursive merge to calculate the size, then the recursive call won't need to be evaluated until the child is needed:

  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

这是全部吗？我不确定并发性。

Is that all? I am not sure about concurrency though.

推荐答案

在懒惰的环境中对WMERGE-3-4C功能没有任何好处。它仍然执行原始下调合并的所有工作。它确实不会让语言系统更容易记住..
在并发环境中无需WMERGE-3-4C功能。对WMERGE-3-4C的每一次呼叫，在将其转移给另一个WMERGE-3-4C的实例之前，都要做好所有的工作。实际上，如果我们用手消除了递归，那么WMERGE-3-4C可以被实现为一个单一的循环，它可以在堆栈中执行所有的工作，然后在堆栈中执行REDUCE的第二个循环。第一个循环并不是自然可行的，尽管REDUCE可能通过并行调用对上的函数来操作，直到只有一个元素保留在列表中。

It doesn’t any benefit to WMERGE-3-4C function in a lazy environment. It still does all the work that the original down-up merge did. It pretty sure it would not be any easier for the language system to memorize.. No benefit to WMERGE-3-4C functions in a concurrent environment. Each call to WMERGE-3-4C does all its work before passing the buck to another instance of WMERGE-3-4C. In fact, if we eliminated the recursion by hand, WMERGE-3-4C could be implemented as a single loop that does all the work while accumulating a stack, then a second loop that does the REDUCE work on the stack. The first loop would not be naturally parallizable, though maybe the REDUCE could operate by calling the function on pairs, in parallel, until only one element remained in the list.

这篇关于重量级左派堆叠：自上而下的合并优势？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！