CODEWITHSUNDEEP
pythondynamic-programming
J P
J P

Reputation: 13

Efficient Dynamic programming using Python

I'm working on a dynamic programming task of finding a minimum cost path along a directed graph (all possible paths have the same number of weighted nodes).

The approach for solving the problem is a recursive function along with a dynamic programming.

Since this dynamic programming task is encountered in many unrelated problems during the code, the concept of threading could be helpful.

The problem is, that in python, 'threading' won't help much. what are efficient ways of handling such a task in python?

Here's the code:

    def rec_fun(pos, path_size, weights, directions):
        cost = weights[d][i, j]
        if path_size == 0:
            key = str(i) + ',' + str(j) + ',' + str(d)
            dict.update({key: pix_cost})
            return cost
        else:
            key = str(i) + ',' + str(j) + ',' + str(d)
            if key in dict:
                return dict[key]
            else:

                val = cost + min(rec_fun(pos + direction[0], path_size - 1, weights, direction),
                                 rec_fun(pos + direction[1], path_size - 1, weights, direction),
                                 rec_fun(pos + direction[2], path_size - 1, weights, direction))
                dict.update({key: val})
                return val

Upvotes: 1

Views: 2327

Answers (2)

rayjc
rayjc

Reputation: 21

With Python 3, you can easily achieve dynamic programming by caching the results of recursive calls using lru_cache from functools.

You can wrap your function as such:

@functools.lru_cache(max_size=None)
def rec_fun(pos, path_size, weights, directions):
    # your code...

Note: Since this caches all calls so it could store more results than you necessarily need compared to implementing DP with your own array or list.

Upvotes: 0

meow
meow

Reputation: 2191

So first off, dynamic programming is just a simple paradigm for solving a certain type of problem. There is not really something specific you can do to optimize dynamic programming in general, in turn that means general python optimizations apply.

So from the code you posted the most striking thing I see is the use of recursions, this is relatively inefficient in python, so start off by moving to for (ideal) or while loops.

Following is a non-exhaustive list of possible ways to make your code run faster in python (with increasing effort):

  1. Try Numba to speed your functions up significantly. It requires very little work (often the @jit decorator is enough) to optimize your code to almost cython level in some cases.

  2. Make use of Numpy to vectorize your code where possible.

  3. Use Processes multiprocessing.Process instead of Threads, as you probably already figured, python threads don't work the same way as in other programming languages due to the global interpreter lock. I think here it's important to note that sharing memory between processes is not really a good practice and you should avoid that if anyhow possible.

  4. Use Python's C-Extension Cython to write all performance critical parts of your code.

Upvotes: 2

Related Questions