My short recursive function takes too long to execute, how can I optimize it

Question

I am trying to solve this problem on CodeChef: http://www.codechef.com/problems/COINS

But when I submit my code, it apparently takes too long to execute, and says the time has expired. I am not sure if my code is inefficient (it doesn't seem like it to me) or if it I am having trouble with I/O. There is a 9 second time limit, to solve maximum 10 inputs, 0 <= n <= 1 000 000 000.

In Byteland they have a very strange monetary system.

Each Bytelandian gold coin has an integer number written on it. A coin n can be exchanged in a bank into three coins: n/2, n/3 and n/4. But these numbers are all rounded down (the banks have to make a profit).

You can also sell Bytelandian coins for American dollars. The exchange rate is 1:1. But you can not buy Bytelandian coins.

You have one gold coin. What is the maximum amount of American dollars you can get for it?

Here is my code: It seems to take too long for an input of 1 000 000 000

def coinProfit(n):
    a = n/2
    b = n/3
    c = n/4

    if a+b+c > n:
        nextProfit = coinProfit(a)+coinProfit(b)+coinProfit(c)
        if nextProfit > a+b+c:
            return nextProfit
        else:
            return a+b+c

    return n

while True:
    try:
        n = input()
        print(coinProfit(n))
    except Exception:
        break

Also, am I correct when if I say that the complexity of my function is going to grow by a power of three? I.e., 3^log_4(n) as worst case? — user50449, Dec 27 '14 at 00:47
I bet input() is your bottleneck. But 9sec for 1G is pretty fair time. — Anonymous, Dec 27 '14 at 00:51
This program never exits, the while loop will go on forever asking for more input. Am I missing something? — superultranova, Dec 27 '14 at 00:51
When I try your program after removing the try/except block in the end, I have a `maximum recursion depth` error each time, no matter `n` — Jivan, Dec 27 '14 at 00:54
@superultranova, not true. the break in the except branch will exit the while loop. — vikingosegundo, Dec 27 '14 at 00:56
For starters, you probably need to `math.floor` the result of `n/2`,... — Willem Van Onsem, Dec 27 '14 at 01:00
@vikingosegundo true, but where is the exception, except the maxiumum recursion exception. I should have said that under normal conditions, the program doesn't exit. The program only exits on error. — superultranova, Dec 27 '14 at 01:00
well, you can run it several time with different input. and kill it with ctrl-c — vikingosegundo, Dec 27 '14 at 01:01
the except is there for the eventual EOF exception, and there is no need to use math.floor because all of the inputs are integers- intege arithmetic. — user50449, Dec 27 '14 at 01:03
@vikingsegundo True, but if you are running it under test with a time limit, and the tester is waiting until the program exits, perhaps that is what is reaching the time limit. I don't know how code chef works, but my guess is that it enforces the time limit on the runtime of the program. — superultranova, Dec 27 '14 at 01:04
Actually it quits if you press enter when it waits for input. — vikingosegundo, Dec 27 '14 at 01:06

score 9 · Accepted Answer · edited Jun 20 '20 at 09:12

The problem is that your code branches each recursive call into three new ones. This leads to exponential behavior.

The nice thing however is that most calls are duplcates: if you call coinProfit with 40, this will cascade to:

coinProfit(40)
 - coinProfit(20)
    - coinProfit(10)
    - coinProfit(6)
    - coinProfit(5)
 - coinProfit(13)
 - coinProfit(10)

What you see is that a lot of effort is repeated (in this small example, coinProfit is called already twice on 10).

You can use Dynamic programming to solve this: store earlier computed results preventing you from branching again on this parts.

One can implement dynamic programing him/herself, but one can use the @memoize decorator to do this automatically.

Now the function does a lot of work way too much times.

import math;

def memoize(f):
    memo = {}
    def helper(x):
        if x not in memo:            
            memo[x] = f(x)
        return memo[x]
    return helper

@memoize
def coinProfit(n):
    a = math.floor(n/2)
    b = math.floor(n/3)
    c = math.floor(n/4)
    if a+b+c > n:
        nextProfit = coinProfit(a)+coinProfit(b)+coinProfit(c)
        if nextProfit > a+b+c:
            return nextProfit
        else:
            return a+b+c
    return n

The @memoize transforms the function such that: for the function, an array of already calculated outputs is maintained. If for a given input, the output has already been computed, it is stored in the array, and immediately returned. Otherwise it is computed as defined by your method, stored in the array (for later use) and returned.

As @steveha points out, python already has a built-in memoize function called lru_cache, more info can be found here.

A final note is that @memoize or other Dynamic programming constructs, are not the solution to all efficiency problems. First of all @memoize can have an impact on side-effects: say your function prints something on stdout, then with @memoize this will have an impact on the number of times something is printed. And secondly, there are problems like the SAT problem where @memoize simply doesn't work at all, because the context itself is exponential (this as far as we know). Such problems are called NP-hard.

Instead of writing your own memoize function, you can use `lru_cache()` decorator (added to Python's `functools` in Python 3.2). For Python older than 3.2 you can get a recipe implementing it: http://stackoverflow.com/questions/11815873/memoization-library-for-python-2-7 — steveha, Dec 27 '14 at 01:12
@steveha: updated with a small remark. I think how the pattern is achieved is not the point of the question, more the ideas behind it. But nice comment anyway ;). — Willem Van Onsem, Dec 27 '14 at 01:14
@steveha notice that `lru_cache` used with no arguments has a default max size of 128 values. The parameter `maxsize` must be set in case you need more (which is the case here). — Jivan, Dec 27 '14 at 01:19
@Jivan I still think it is a win to use the standard `lru_cache()` rather than rolling your own, even if you do need to set `maxsize`. — steveha, Dec 27 '14 at 01:33
@steveha I didn't say it's better to roll your own. Definitely use `lru_cache()`, but just don't forget to set `max_size` if needed :) — Jivan, Dec 27 '14 at 01:40
@steveha: it is indeed better to use the library implementation. The answer however aims to demonstrate how such `@memoize` decorator works, and thus provides some source code. Furthermore by using a *memoize*, pattern the time-complexity drops to polynomial behavior. of course by using a library, one can gain additional performance, however in big-oh, nothing changes, and if one experiments with this code, it runs good enough on input of about `1G`. — Willem Van Onsem, Dec 28 '14 at 18:07

score 1 · Answer 2 · answered Dec 27 '14 at 01:10

You can optimize the program by storing result in some sort of cache. So if the result exist in cache then no need to perform the calculation , otherwise calculate and put the value in the cache. By this way you avoid calculating already calculated values. E.g.

cache = {0: 0}


def coinProfit(num):
    if num in cache:
        return cache[num]
    else:
        a = num / 2
        b = num / 3
        c = num / 4
        tmp = coinProfit(c) + coinProfit(b) + coinProfit(a)
        cache[num] = max(num, tmp)
        return cache[num]


while True:
    try:
        print coinProfit(int(raw_input()))
    except:
        break

score 0 · Answer 3 · answered Dec 27 '14 at 01:10

I just tried and noticed a few things... This doesn't have to be considered as The answer.

On my (recent) machine, it takes a solid 30 seconds to compute with n = 100 000 000. I imagine that it's pretty normal for the algorithm you just wrote, because it computes the same values times and times again (you didn't optimise your recursion calls with caching as suggested in other answers).

Also, the problem definition is pretty gentle because it insists: each Bytelandian gold coin has an integer number written on it, but these numbers are all rounded down. Knowing this, you should be turning the three first lines of your function into:

import math

def coinProfit(n):
    a = math.floor(n/2)
    b = math.floor(n/3)
    c = math.floor(n/4)

This will prevent a, b, c to be turned into float numbers (Python3 at least) which would make your computer go like crazy into a big recursive mess, even with the smallest values of n.

Even better would be to use Python's `//` operator, integer division: `a = n // 2` and so on. Available even in Python 2.x. — steveha, Dec 27 '14 at 01:14

My short recursive function takes too long to execute, how can I optimize it

3 Answers3