Parallelisingツリーは、再帰的な手順

Question

は、私は長い間、実行中のタスクを並列化したい

let count_change amount = 

    let first_denomination kinds_of_coins = 
     match kinds_of_coins with 
     |1->1 
     |2->5 
     |3->10 
     |4->25 
     |5->50 

    let rec cc amount kinds_of_coins = 
     match (amount,kinds_of_coins) with 
     |(0,_) -> 1 
     |(i,j) when i<0 || j=0 -> 0 
     |(_,_) -> 
      [cc amount (kinds_of_coins-1) + 
      cc (amount - (first_denomination kinds_of_coins)) kinds_of_coins] 
       |> List.fold (+) 0 

    cc amount 5 

次のようにF＃でSICPから変更回数の問題を書いて、これは私が

let rec cc amount kinds_of_coins = 
    match (amount,kinds_of_coins) with 
    |(0,_) -> 1 
    |(i,j) when i<0 || j=0 -> 0 
    |(_,_) -> 
     [async {return cc amount (kinds_of_coins-1) 
     + cc (amount - (first_denomination kinds_of_coins)) kinds_of_coins}] 
     |> Async.Parallel |> Async.RunSynchronously |> Array.fold (+) 0 

これをやったことあります最初の実装よりも数オーダー遅いです。どうすればより効果的に並列化できるのか教えてください。

Answer 1

私は間違っている可能性がありますが、並列化のための深さの最初の探索の代わりに幅優先探索を行う必要があると思います。

Answer 2

これはまったく平行ではありません。あなたは単なる並行して単一のタスクを起動しますが、それは単純な方法よりも悪いです。 また、関数が末尾再帰型ではないので、常に安全であるとは限りません。 とにかく私は考えることができる並列処理を導入する最も簡単な方法は次のとおりです。

let rec cc (amount,kinds_of_coins) = 
    match (amount,kinds_of_coins) with 
    |(0,_) -> 1 
    |(i,j) when i<0 || j=0 -> 0 
    |(_,_) -> 
     [| (amount,(kinds_of_coins-1)); 
      ((amount - (first_denomination kinds_of_coins)), kinds_of_coins) 
     |] |> Array.Parallel.map(cc) |> Array.fold (+) 0 

しかし、私は、これはオリジナルよりもはるかに高速になり、あなたを保証するものではありません。