[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

What make function with huge list so slow

'I'm just running them in succession and seeing how long they'. The full
code looks like this, this is only an example.py here. and I run 'time
python3 example.py' for each function.

    def fib_dp(n):
        dp = [0] * (n+1)
        if n <= 1:
            return n
        dp[0], dp[1] = 0, 1
        for i in range(2, n+1):
            dp[i] = dp[i-1] + dp[i-2]
        return dp[-1]

    def fib_dp2(n):
        # add dp here just for calculating memory allocation time
        dp = [0] * (n+1)
        if n <= 1:
            return n
        pre, now = 0, 1
        for i in range(2, (n+1)):
            pre, now = now, pre+now
        return now

    # run the function only once
    # fib_dp(400000) # took more than 60s
    # fib_dp2(400000) # took about 2s