Распараллеливание дерева рекурсивной процедуры

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

Это совсем не параллельно. Вы просто запускаете параллельно одну задачу, что хуже, чем выполнять ее простым способом. Также помните, что ваша функция не является рекурсивной, поэтому она не всегда может быть безопасной. В любом случае, самый быстрый способ ввести параллелизм, о котором я могу думать, это:

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

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

Answer 2

Я могу ошибаться, но я думаю, что для параллелизации вам понадобится сначала пройти в ширину, а не в глубину, чтобы показать какую-либо выгоду.