Efficiently calculate value of Pascal's Triangle using memoization and recursion

Question

So reading about functional programming, applications to dynamic programming, and learning Scala. I figured I would try it out with a popular example, Pascal's Triangle, tests against known values work out fine. Any tips for optimization? Am I doing anything totally wrong? Is there a way to do this with tail recursion that I'm missing? Any feedback appreciated.

def pascal(c: Int, r: Int): Int = {
    // use a cache; map if (c,r) pair to value
    // fill in value recursively
    var cache: Map[(Int,Int), Int] = Map()
    cache += ((0,0) -> 1)
    var i = 0
    for(i <- 1 to r){
       cache += ((0,i) -> 1)
       cache += ((i,i) -> 1)
    } 

    def getPascalValue(c: Int, r: Int): Int = {
        if (cache.contains((c, r))) {
            cache((c, r))
        } else {
            cache += ((c, r) -> (getPascalValue(c, r - 1) + getPascalValue(c - 1, r - 1)))
            cache((c, r))
        }
    }
    getPascalValue(c,r)
}

tested with values c=5 and r=109 and the runtime was quite long, so there seems to be an issue with the cache — Martin Boros
– Martin Boros, Commented Mar 19, 2021 at 19:49
Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. — Mast
– Mast ♦, Commented Mar 21, 2021 at 19:48
Feel free to ask a new question instead, with a hyperlink to this question for bonus context. — Mast
– Mast ♦, Commented Mar 21, 2021 at 19:48
If you want to show everyone how you improved your code, but don't want to ask another question, then post an answer to your own question. So it would be okay to post the updated code as an answer to this question? — Martin Boros
– Martin Boros, Commented Mar 21, 2021 at 20:05
Only if the answer would be written like a review. That is, it should point out why the original code was wrong and make insightful remarks about the code. You can add parts from other answers (please give credit where applicable) but also your own remarks. Feel free to add the new code to the end of it. — Mast
– Mast ♦, Commented Mar 22, 2021 at 17:23

jwvh · Accepted Answer · 2021-03-20 09:15:10Z

2

Your code is clearly organized and well presented, but it suffers from a number of problems, from the trivial to the profound.

var i = 0 is never used and doesn't need to be there.
safety: There's no check for bad input. pascal(2,1) will happily java.lang.StackOverflowError.
Your code indicates a lack of familiarity with the Scala Standard Library. Initializing the cache, for example, can be accomplished with a single statement.

var cache: Map[(Int,Int), Int] =
  (0 to r).flatMap(n => Seq((0,n)->1, (n,n)->1)).toMap

Likewise, instead of an immutable Map in a var variable for the cache, if you use a mutable Map in a val variable then getPascalValue() can be reduced to a single statement.

def getPascalValue(c: Int, r: Int): Int =
  cache.getOrElseUpdate((c,r), getPascalValue(c, r-1) +
                               getPascalValue(c-1, r-1))

But the real problem here is that you're putting in a lot of overhead for no reward.

small problem: The cache is initialized with some values that may never be referenced.
big problem: The cache is updated with values that will never be referenced.

That's right. Nothing added to the cache, after initialization, serves any purpose. It's just inefficient busywork.

And the reason your cache isn't working: each iteration (recursion) starts with the original, initialized, cache. That version is updated, +=, with the newly computed pascal number, but that update is lost when the stack frame pops and execution returns to the caller.

edited Mar 20, 2021 at 9:15

answered Mar 20, 2021 at 7:58

jwvh

1,4738 silver badges10 bronze badges

\$\begingroup\$ Very helpful, thanks. Updated code with your suggestions and the cache is working properly now \$\endgroup\$

Martin Boros
– Martin Boros

2021-03-21 18:29:12 +00:00
Commented Mar 21, 2021 at 18:29
1

\$\begingroup\$ Thanks. I'm glad you found this helpful. I'm surprised you say the cache is working properly. I didn't offer a fix for the cache problem because I don't know of an easy way to fix it. I'd be interested to learn how you fixed it and/or how you tested it to show it was fixed. \$\endgroup\$

jwvh
– jwvh

2021-03-22 07:13:48 +00:00
Commented Mar 22, 2021 at 7:13
\$\begingroup\$ Yeah just switching to a mutable map and using the getOrElseUpdate method was enough to get the cache working, testing based on run time for pascal(5, 105) run time dropped from 20s to 3ms, link to updated code: codereview.stackexchange.com/questions/257554/… \$\endgroup\$

Martin Boros
– Martin Boros

2021-03-23 02:48:21 +00:00
Commented Mar 23, 2021 at 2:48
2

\$\begingroup\$ Oh my. You're right. The compiler recognizes the differences between an immutable collection in a var and a mutable collection in a val. Smart compiler. \$\endgroup\$

jwvh
– jwvh

2021-03-23 05:44:09 +00:00
Commented Mar 23, 2021 at 5:44

Add a comment |

Stack Exchange Network

Efficiently calculate value of Pascal's Triangle using memoization and recursion

1 Answer 1

You must log in to answer this question.

Hot Network Questions

Efficiently calculate value of Pascal's Triangle using memoization and recursion

1 Answer 1

You must log in to answer this question.

Related

Hot Network Questions