3

I came across a weird phenomenon:

I wrote a code to calculate "Catalan Numbers", which works , but now I'm trying to improve run-time by using a Memoization dictionary (called it dicatalan):

dicatalan = {} 
def catalan(n):
    if n == 0:
        return 1
    else: 
        res = 0
        if n not in dicatalan:
            for i in range(n):
                res += catalan(i) * catalan(n - i - 1)
            dicatalan[n] = res
            print ("dicatalan is", dicatalan)
    return dicatalan[n]

Here's the catch - In eclipse - Pydev - for n=1 the code runs halfway and prints as expected: "dicatalan is 1:1" before stopping mysteriously, but in IDLE the same code prints "dicatalan is 0:1" .

Any case, when trying to print later dicatalan I received {}.

How could that be? what happens in the code? running debugger proved futile.

Any ideas for making the dict work?

Andy Hayden
  • 359,921
  • 101
  • 625
  • 535
jizanthapus
  • 121
  • 1
  • 9
  • I don't think that you ever store 0 in the dicatalan, which is the cause of further problems. – sega_sai Dec 08 '12 at 14:13
  • 2
    After indenting the code, it works just fine here (the dict contents, the prints, the result). Can you confirm your indentation is the same one after my edit on your post ? – mmgp Dec 08 '12 at 14:22
  • @mmgp I can confirm the code works fine for me :) – Vincenzo Pii Dec 08 '12 at 14:24
  • This also works fine for me. There is a library which does memoisation in functools: http://stackoverflow.com/a/12562777/1240268 – Andy Hayden Dec 08 '12 at 14:33

1 Answers1

1

Works fine for me too, I took the liberty of simplifying your code a little:

def catalan(n, memo={0: 1}):
  if n not in memo:
    memo[n] = sum((catalan(i) * catalan(n - i - 1)) for i in range(n))
  return memo[n]
wim
  • 338,267
  • 99
  • 616
  • 750
  • Hello all, I feel funny now. Probably the problem derived from wrong syntax (dicatalan[(n)])...After copying the indented code (thanks mmgp) - Now it works to me as well. sega_sai - you're right, yet it doesn't inflict the deserved outcome... wim - very elegant, lovely one. Thanks you all very much. – jizanthapus Dec 08 '12 at 15:49
  • @user1868486 just a clarification: `dicatalan[(n)]` is totally equivalent to `dicatalan[n]`, so that is not what caused the problem. Also, I didn't do this change, it was further edited by someone else. But I changed the indentation to what seemed sensible to me, so if you still have your original code you can compare it to my indentation edit (you can check what edits were made by clicking on the link "edit X hours ago" at the bottom of your post). – mmgp Dec 08 '12 at 16:15