Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to speed up a recursive algorithm

I'm trying to solve the Hackerrank challenge Game of Stones, a (shortened) problem statement of which is copied below.

enter image description here

I came up with the following solution:

# The lines below are for the Hackerrank submission
# T = int(raw_input().strip())
# ns = [int(raw_input().strip()) for _ in range(T)]

T = 8
ns = [1, 2, 3, 4, 5, 6, 7, 10]

legal_moves = [2, 3, 5]

def which_player_wins(n):
    if n <= 1:
        return "Second"               # First player loses
    elif n in legal_moves:
        return "First"                # First player wins immediately
    else:
        next_ns = map(lambda x: n - x, legal_moves)
        next_ns = filter(lambda x: x >= 0, next_ns)
        next_n_rewards = map(which_player_wins, next_ns)      # Reward for opponent
        if any(map(lambda x: x=="Second", next_n_rewards)):            # Opponent enters a losing position
            return "First"
        else:
            return "Second"

for n in ns:
    print which_player_wins(n)

The algorithm is essentially the minimax algorithm as it looks one move ahead and then recursively calls the same function. The problem is that in Hackerrank, it is terminating due to timeout:

enter image description here

Indeed, I've noticed that evaluating which_player_wins(40) already takes ~2 seconds. Any ideas for a faster solution which would not time out?

like image 878
Kurt Peek Avatar asked Aug 28 '16 12:08

Kurt Peek


People also ask

How do you improve recursion performance?

Bottom-up. Sometimes the best way to improve the efficiency of a recursive algorithm is to not use recursion at all. In the case of generating Fibonacci numbers, an iterative technique called the bottom-up approach can save us both time and space.

Why is my recursive function so slow?

Recursion is slower and it consumes more memory since it can fill up the stack. But there is a work-around called tail-call optimization which requires a little more complex code (since you need another parameter to the function to pass around) but is more efficient since it doesn't fill the stack.

Are recursive algorithms faster?

The simplicity of recursion comes at the cost of time and space efficiency. It is much slower than iteration due to the overhead of function calls and control shift from one function to another. It requires extra memory on the stack for each recursive call.

How do you make a recursive function faster in Python?

Caching recurve function is one way to improve this function speed. There is a standard Python library called functools . It has a memory caching function lru_cache . It could be used as a Python decorator.


2 Answers

It seems from the problem description that you are able to keep the intermediate and final results from each calculation to use in later calculations. If that is so, a recursive algorithm is not optimal. Instead, use a dynamic programming style.

In other words, keep a global array that stores the results from previous determinations of wins and losses. When you determine for a new value of n, rather than recursing all the way to the end, use the previous determinations.

For example, when you get to n=10, you see that the first player removing 3 stones leaves 7 stones, which you have already seen as a win for the second player. Therefore, 10 stones is a win for the first player.

I believe that your recursive algorithm would calculate all over again the result for n=7 rather than using the previous work.

like image 98
Rory Daulton Avatar answered Oct 10 '22 22:10

Rory Daulton


Your solution would work (though very slowly) if you had infinite recursion levels available. But since you're not re-using already calculated results you are very quickly hitting Python's recursion limit. One good solution, as suggested above, is to re-write the code using a non-recursive algorithm.

Alternatively, you could keep the code you have, but get it to re-use any result that you've already seen before. This is called memoization, and an easy way to implement that is to add a memoization decorator to the part of the code that computes the next move. Here's a way to use memoization to speed up your recursive algorithm, which I think is what you've specifically asked for:

  1. Convert all of the code after the first else into a function, next_move(n) that returns either 'First' or 'Second'.

  2. Add a memoize(f) function which will take next_move(n) and avoid the recursion call if the result for n has already been calculated.

  3. Add the decorator line @memoize immediately before the next_move definition.

Resulting code:

T = 8
ns = [1, 2, 3, 4, 5, 6, 7, 10]

legal_moves = [2, 3, 5]

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

@memoize
def next_move(n):
    next_ns = map(lambda x: n - x, legal_moves)
    next_ns = filter(lambda x: x >= 0, next_ns)
    next_n_rewards = map(which_player_wins, next_ns)  # Reward for opponent
    if any(map(lambda x: x == "Second", next_n_rewards)):  # Opponent enters a losing position
        return "First"
    else:
        return "Second"

def which_player_wins(n):
    if n <= 1:
        return "Second"               # First player loses
    elif n in legal_moves:
        return "First"                # First player wins immediately
    else:
        return next_move(n)

for n in ns:
    print which_player_wins(n)

This hugely speeds up the calculation as well as reducing the levels of recursion required. On my computer n=100 is solved in 0.8 ms.

like image 38
MichaelMaggs Avatar answered Oct 10 '22 22:10

MichaelMaggs