freesoul's blog

Can somebody help me in making this python code run faster ? Similar C++ code got accepted easily. problem SPOJ COUNT
By freesoul, 8 years ago, In English 
dp = [[0 for i in xrange(5005)] for i in xrange(5005)]
def f_f(c,t):
    if (dp[c][t] != 0): 
        return dp[c][t] - 1;
    if (t==1):
        return 1;
    ret = 0
    i = int(c/t)
    while(i >= 0):
        ret=ret+ f_f (c-i*t, t-1)
        if ret >= 1988:
            ret %= 1988
        i = i - 1
    dp[c][t] = 1 + ret
    return dp[c][t] - 1

while(1):
    o = raw_input();
    s = map(int,o.split())
    a = s[0]
    b = s[1]
    if (a == 0 and b == 0):
        break
    print f_f(a-b,b)
  • Vote: I like it
  • -8
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Zlobober mentions in a comment here that wrapping your program in a function can speed it up.

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Slowness aside, I ran this code on my computer with 5000 5000 as input and got a stack overflow (with both CPython and PyPy).

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

first:

replace
  if ret >= 1988:
      ret %= 1988
by
  if ret >= 1988:
      ret -= 1988

second: get rid of recursion

for i in range(0, 5001):
    dp[i][1] = 0
for t in range(2, 5001):
   for c in range(0, 5001):
      // calc dp[c][t] like in your f_f function, but instead of call f_f use dp[x][y], all needed values are already calculated.
→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeah, I wanted to say the same about the recursion—and it has to be removed or improved to fix the stack overflow anyway—but when I actually tried to remove the recursion, the DP loop ran so slow that I didn’t have the patience to wait for it to finish under CPython. Even under PyPy, it took more than 70 seconds on my machine (a 2010 laptop with a then-high-end Core i7).

    I don’t think your suggestion about the modulus operator helps at all though. In fact, I’d suggest doing exactly the opposite: just ret %= 1998 without any conditions; but that doesn’t affect performance either.

    There’s plenty of small things that are too slow or just horrible in this piece of Python, but changing none of them gave any measurable impact on the performance in my tests.

    The only thing that helped was wrapping all code in a function like the comment above said. That actually reduced the runtime by a third! And in both CPython and PyPy.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think %= is slower than if and -=
      Also can help single one %= after while loop.

      → Reply
»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Sometimes regardless of no matter how you speed it up it won't pass, especially on sites like SPOJ that are most anti anything but C++. Many times JAVA doesn't even pass on SPOJ ( like literally no single accepted solution), so let alone Python.

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

the complexity of your code is actually O(N * N * log(N)) but you can reduce it to O(N * N> By using prefix sums , the normal recurrence is dp[n][k] = sum(dp[n — i * k][k — 1]) , but you can use prefix sum here , you can create another dp like dp2[n][k] denotes sum of all dp[n][k] + dp[n — i * (k + 1)][k] and then dp[n][k] will just be equal to dp2[n][k] and dp2[n][k] can be updated like dp2[n][k] = dp2[n — k — 1][k] + dp[n][k] . Here is the code . Edit , you dont even need prefix sum , just change the recurance to dp[n][k] = dp[n][k — 1] + dp[n — k][k] and done. code

→ Reply