Блог пользователя freesoul

Can somebody help me in making this python code run faster ? Similar C++ code got accepted easily. problem SPOJ COUNT
Автор freesoul, 9 лет назад, По-английски 
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)
  • Проголосовать: нравится
  • -8
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.
→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить
»
9 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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.

→ Ответить
»
9 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить