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(限られた数の再帰呼び出しのみを行いたいため) を保持する必要がありますが、継続を使用する必要はありません (深さがかなり制限されており、新しいタスクを開始するときに、とにかくスタックを保持しません）。

これは、2 つの側面を組み合わせる必要がまったくないことを意味します。次に、並列バージョンを非常に簡単な方法で書き直すことができます。

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の場合は現在のツリーで呼び出すことができるため、コードを複製する必要はありませんtree when depth <= 0。

Task<int>これはまた、代わりに作成することで参照セルの使用を回避しTask、アルゴリズムを変更して、1 つのバックグラウンド タスクのみを生成し、現在のスレッドで作業の 2 番目の部分を実行します。

于 2012-06-27T20:47:48.020 に答える
2

私の目には、深さは問題ないように見えますが、醜い部分は ref セルと割り当てです。なぜそれらが必要なのかわかりません。パラメータidとして（恒等関数）を渡すだけで、値が返されるため、参照セルは必要ないと思います。（私は間違っているかもしれません。これは一目でわかる分析です。）contsumRec

(また、スタイルの問題として、再帰呼び出しサイトを取り除きnewDepth、単にインライン化します。)(depth-1)

最後に、何が何なのかわかりませんが、代わりにsumTreeContMonad使用するだけで同じように機能するようです。sumRec t -1 ksumTreeContMonad t k

(ブログにコードの写真ではなくコードが含まれていた場合、これらの改良を加えた独自のコードを投稿するだけかもしれませんが、データ型などを書き写す気はありません。なぜ写真を投稿するのですか?)

于 2012-06-27T20:08:04.563 に答える