Parallelising дерево рекурсивная процедура

Question

Я написал проблему подсчета изменения от SICP в F # следующим образом

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 

Я хотел распараллелить долго выполняющиеся задачи, и это то, что я сделал

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 

Но я не гарантирую вам это будет гораздо быстрее, чем оригинал.