3

我正在尝试使用任务并行库对树求和，其中子任务仅在遍历树直到一定深度之前才产生，否则它使用连续传递样式对剩余的子节点求和，以避免堆栈溢出。

然而，代码看起来很丑 - 使用状态单子来携带当前深度会很好，但状态单子不是尾递归的。或者，我将如何修改延续单子以携带状态？或者创建状态和延续单子的组合？

let sumTreeParallelDepthCont tree cont = 
  let rec sumRec tree depth cont =
    let newDepth = depth - 1
    match tree with
    | Leaf(num) -> cont num
    | Branch(left, right) ->
      if depth <= 0 then
        sumTreeContMonad left (fun leftM ->
          sumTreeContMonad right (fun rightM ->
            cont (leftM + rightM )))
      else 
        let leftTask = Task.Factory.StartNew(fun () -> 
              let leftResult = ref 0
              sumRec left newDepth (fun leftM -> 
                leftResult := leftM)
              !leftResult
              )
        let rightTask = Task.Factory.StartNew(fun () -> 
              let rightResult = ref 0
              sumRec right newDepth (fun rightM ->
                rightResult := rightM)
              !rightResult
              )
        cont (leftTask.Result + rightTask.Result)
  sumRec tree 4 cont // 4 levels deep

我在这篇博文中有更多细节：http: //taumuon-jabuka.blogspot.co.uk/2012/06/more-playing-with-monads.html

4

2 回答 2

6

我认为首先了解您的要求很重要。

  • 算法的顺序版本不需要保留depth（因为它总是处理树的其余部分）。但是，它需要使用延续，因为树可能很大。

  • 另一方面，并​​行版本需要保留depth（因为您只想进行有限数量的递归调用），但不需要使用延续（因为深度非常有限并且当您开始一个新任务时，它无论如何都不会保留堆栈）。

这意味着您根本不需要将这两个方面结合起来。然后你可以用一种非常直接的方式重写并行版本：

let sumTreeParallelDepthCont tree =  
  let rec sumRec tree depth = 
    match tree with 
    | Leaf(num) -> num 
    | tree when depth <= 0 -> 
        sumTreeContMonad tree id
    | Branch(left, right) ->
        let leftTask = Task.Factory.StartNew(fun () -> sumRec left (depth + 1))
        let rightResult = sumRec right (depth + 1)
        leftTask.Result + rightResult
  sumRec tree 4 // 4 levels deep

无需复制代码，sumTreeContMonad因为您可以在 case 的当前树上调用它tree when depth <= 0。

Task<int>这也通过创建而不是避免使用参考单元格，Task并且我修改了算法以仅生成一个后台任务并在当前线程上执行第二部分工作。

于 2012-06-27T20:47:48.020 回答
2

在我看来，深度看起来不错，丑陋的一点是参考单元格和分配。我不清楚你为什么需要它们；我认为只是将id(identity function) 作为cont参数传递意味着sumRec将返回该值，然后您将不需要参考单元格。（我可能错了，这是一目了然的分析。）

（作为风格问题，我也将摆脱newDepth并在递归调用站点内联。）(depth-1)

最后，我不知道是什么sumTreeContMonad，但看起来你可以只使用sumRec t -1 k而不是，sumTreeContMonad t k它的工作原理是一样的。

（如果你的博客有代码，而不是代码图片，我可能会发布我自己的代码进行这些改进，但我不想转录数据类型等。为什么要发布图片？）

于 2012-06-27T20:08:04.563 回答