Have Geek Brain

Parallel recursive tree procedure

I wrote a change counter issue from sicp in F # as follows

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

I wanted to parallelize a long running task and this is what I did

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

This is slower than the first multi-order implementation. Could you please tell me how I could parallelize it more efficiently.

0


a source to share


2 answers


I could be wrong, but I think you will need to do the first pass, not the depth, the first for parallelization to show any benefit.



+2


a source


It is not parallel. You are just running a parallel task, which is worse than simple. Also, remember that your function is not recursive, so it may not always be safe. Anyway, the fastest way to represent parallelism that I can think of is:

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


But I cannot guarantee that it will be much faster than the original.

+2


a source






More articles:


All Articles