12

我正在研究冈崎的纯功能数据结构并尝试构建 F# 实现。我也在完成书中列出的练习（有些非常具有挑战性）。好吧，我坚持练习 3.4，它要求修改 WeightBiasedLeftistHeap 的合并函数，使其在单遍中执行，而不是原来的 2 遍实现。

我还没有弄清楚如何做到这一点，并希望得到一些建议。SO上有另一篇文章，其中一个人通过几乎内联makeT函数在SML中做到这一点。我开始走这条路线（在评论的第 3.4 节第一次尝试中。但放弃了这种方法，因为我认为这真的不是一次执行（它仍然会'直到到达叶子然后展开并重建树）。我将其解释为仍然是两次合并是错误的吗？

这是我完整实现 WeightBiasedLeftistHeap 的链接。

这是我在 F# 中失败的尝试：

type Heap<'a> =
| E
| T of int * 'a * Heap<'a> * Heap<'a> 

module WeightBiasedLeftistHeap =
    exception EmptyException

    let weight h =
        match h with
        | E -> 0
        | T(w, _,_,_) -> w

    let makeT x a b =
        let weightA = weight a
        let weightB = weight b
        if weightA >= weightB then
            T(weightA + weightB + 1, x, a, b)
        else
            T(weightA + weightB + 1, x, b, a)

    // excercise 3.4 first try
    //    let rec merge3_4 l r =
    //        match l,r with
    //        | l,E -> l
    //        | E,r -> r
    //        | T(_, lx, la, lb) as lh, (T(_, rx, ra, rb) as rh) ->
    //            if lx <= rx then
    //                let right = merge3_4 lb rh
    //                let weightA = weight la
    //                let weightB = weight right
    //
    //                if weightA >= weightB then
    //                    T(weightA + weightB + 1, lx, la, right)
    //                else
    //                    T(weightA + weightB + 1, lx, right, la)
    //            else
    //                let right = merge3_4 lh rb
    //                let weightA = weight ra
    //                let weightB = weight right
    //
    //                if weightA >= weightB then 
    //                    T(weightA + weightB + 1, rx, ra, right)
    //                else
    //                    T(weightA + weightB + 1, rx, right, ra)

    // excercise 3.4 second try (fail!)
    // this doesn't work, I couldn't figure out how to do this in a single pass
    let merge3_4 l r =
        let rec merge' l r value leftChild  =
            match l,r with
            | l,E -> makeT value leftChild l
            | E,r -> makeT value leftChild r
            | T(_, lx, la, lb) as lh, (T(_, rx, ra, rb) as rh) ->
                if lx <= rx then
                    merge' lb rh lx la   //(fun h -> makeT(lx, la, h))
                else
                    merge' lh rb rx ra   //(fun h -> makeT(rx, ra, h))

        match l, r with
        | l, E -> l
        | E, r -> r
        | T(_, lx, la, lb) as lh, (T(_, rx, ra, rb) as rh) ->
            let lf = fun h -> makeT(lx, la, h)
            if lx <= rx then
                merge' lb rh lx la // (fun h -> makeT(lx, la, h))
            else
                merge' lh rb rx ra // (fun h -> makeT(rx, ra, h))

    let rec merge l r =
        match l,r with
        | l,E -> l
        | E,r -> r
        | T(_, lx, la, lb) as lh, (T(_, rx, ra, rb) as rh) ->
            if lx <= rx then
                makeT lx la (merge lb rh)
            else
                makeT rx ra (merge lh rb)

    let insert3_4 x h =
        merge3_4 (T(1,x,E,E)) h
4

2 回答 2

23

第一个问题是：什么是“一次通过”算法？可以自然地实现为单个自上而下循环的东西将符合条件。相比之下，递归——天真地编译——通常有两次通过，一次在向下的路上，一次在向上的路上。 尾递归可以很容易地编译成循环，并且通常是函数式语言。 尾递归模 cons是一种类似的优化，尽管不太常见。但是，即使您的编译器不支持尾递归模 cons，您也可以轻松地将此类实现手动转换为循环。

尾递归模 cons 与普通尾递归类似，只是尾调用被包裹在构造函数中，可以在递归调用之前分配和部分填充。在这种情况下，您可能希望返回表达式类似于T (1+size(a)+size(b)+size(c),x,a,merge(b,c)). 此处所需的关键见解（如另一个 SO 线程的编辑中所述）是您无需执行合并即可知道结果将有多大，因此它应该在新树的哪一侧继续。这是因为 的大小merge(b,c)将始终为size(b)+size(c)，可以在合并之外计算。

请注意，rank普通左派堆的原始函数不共享此属性，因此无法以这种方式进行优化。

然后，本质上，您将两个调用内联到 makeT并将表单的调用转换size(merge(b,c))为size(b)+size(c).

进行此更改后，生成的函数会比原始函数显着延迟，因为它可以在评估递归合并之前返回结果的根。

类似地，在涉及锁和变异的并发环境中，新实现可以通过为每个节点获取和释放锁来支持更多的并发性，而不是锁定整个树。（当然，这只对非常轻量级的锁有意义。）

于 2011-06-14T02:21:12.693 回答
2

我不确定我是否正确理解了这个问题，但这是我的尝试 - 目前，该merge操作执行递归调用merge（这是第一遍），并且当它到达堆的末尾时（前两种情况match），它将新构建的堆返回给调用者并调用makeT几次（这是第二遍）。

我不认为简单的内联mMakeT是我们被要求做的（如果是，只需添加inline即可makeT，这样做不会降低代码的可读性:-)）。

但是，可以做的是修改merge函数以使用连续传递样式，其中“其余工作”作为函数传递给递归调用（因此堆栈上没有待处理的工作在之后完成第一遍完成）。这可以这样做：

let rec merge' l r cont =
    match l,r with
    | l,E -> cont l // Return result by calling  the continuation
    | E,r -> cont r // (same here)
    | T(_, lx, la, lb) as lh, (T(_, rx, ra, rb) as rh) ->
        if lx <= rx then
            // Perform recursive call and give it 'makeT' as a continuation
            merge' lb rh (makeT lx la)
        else
            // (same here)
            merge' lh rb (makeT rx ra)

// Using 'id' as a continuation, we just return the 
// resulting heap after it is constructed
let merge l r = merge' l r id

我不完全相信这是正确的答案 - 它只执行一次传递，但汇总的工作（在继续中）意味着传递时间长两倍。但是，我看不出有什么方法可以让这件事变得更简单，所以它可能是正确的答案......

于 2011-06-13T19:39:16.143 回答