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

Я написал задачу подсчета изменений из 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

Это работает медленнее первой реализации на несколько порядков. Не могли бы вы рассказать мне, как я мог бы распараллелить это более эффективно.


f# parallel-processing
person Community    schedule 27.05.2009    source источник

Ответы (2)


arrow_upward
2
arrow_downward

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

person leppie    schedule 27.05.2009
comment
На самом деле обход в глубину дает гораздо большее преимущество в эффективности, когда дело доходит до параллелизма. - person Noldorin; 27.05.2009

arrow_upward
2
arrow_downward

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

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

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

person em70    schedule 27.05.2009