1

我正在从事一项动态编程任务，即沿着有向图查找最小成本路径（所有可能的路径都具有相同数量的加权节点）。

解决问题的方法是递归函数和动态规划。

由于在代码过程中会遇到许多不相关的问题，因此线程的概念可能会有所帮助。

问题是，在 python 中，“线程”没有多大帮助。在 python 中处理此类任务的有效方法是什么？

这是代码：

    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
4

2 回答 2

2

所以首先，动态规划只是解决某种类型问题的简单范例。一般来说，您无法做一些具体的事情来优化动态编程，这反过来意味着应用了一般的 python 优化。

所以从你发布的代码中我看到的最引人注目的是递归的使用，这在 python 中效率相对较低，所以从移动到for（理想的）或while循环开始。

以下是使您的代码在 python 中运行得更快的可能方法的非详尽列表（通过越来越多的努力）：

  1. 尝试Numba显着加快您的功能。在某些情况下，只需很少的工作（通常@jit装饰器就足够了）将您的代码优化到几乎 cython 级别。

  2. 尽可能使用Numpy对代码进行矢量化。

  3. 正如您可能已经想到的那样，使用进程multiprocessing.Process而不是线程，由于全局解释器锁定，python 线程的工作方式与其他编程语言不同。我认为在这里重要的是要注意在进程之间共享内存并不是一个好的做法，如果可能的话，你应该避免这种情况。

  4. 使用 Python 的 C-Extension Cython编写代码的所有性能关键部分。

于 2018-06-21T18:23:21.267 回答
0

使用 Python 3，您可以通过使用functools中的lru_cache缓存递归调用的结果来轻松实现动态编程。

你可以这样包装你的函数：

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

注意：由于这会缓存所有调用，因此与使用您自己的数组或列表实现 DP 相比，它可以存储比您需要的更多的结果。

于 2020-01-03T21:37:28.123 回答