3
\$\begingroup\$

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)
}
\$\endgroup\$
5
  • 1
    \$\begingroup\$ tested with values c=5 and r=109 and the runtime was quite long, so there seems to be an issue with the cache \$\endgroup\$ Mar 19, 2021 at 19:49
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – Mast
    Mar 21, 2021 at 19:48
  • \$\begingroup\$ Feel free to ask a new question instead, with a hyperlink to this question for bonus context. \$\endgroup\$
    – Mast
    Mar 21, 2021 at 19:48
  • \$\begingroup\$ 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? \$\endgroup\$ Mar 21, 2021 at 20:05
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – Mast
    Mar 22, 2021 at 17:23

1 Answer 1

2
\$\begingroup\$

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.

\$\endgroup\$
4
  • \$\begingroup\$ Very helpful, thanks. Updated code with your suggestions and the cache is working properly now \$\endgroup\$ 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
    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\$ 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
    Mar 23, 2021 at 5:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.