时间戳

首页 > 解决方案 > 为什么我的代码查找大数字组合的速度如此之慢？

python - 为什么我的代码查找大数字组合的速度如此之慢？

问题描述

我的代码查找具有给定总和的数字列表的所有组合。代码运行良好，但在尝试大数字（如 100 或 200）时，代码花费的时间太长。
关于如何使代码更快的任何建议？

def check(target, lst):
    def _a(idx, l, r, t):
        if t == sum(l): r.append(l)
        elif t < sum(l): return
        for u in range(idx, len(lst)):
            _a(u, l + [lst[u]], r, t)
        return r
    return len(_a(0, [], [], target))


print(check(200, (1, 2, 5, 10, 20, 50, 100, 200, 500)))

标签： pythonperformanceoptimization

解决方案

让内部函数更简单（只给它索引和剩余目标，并返回数字）然后记忆它？

from functools import lru_cache

def check(target, lst):
    @lru_cache(None)
    def a(idx, t):
        if t == 0: return 1
        elif t < 0: return 0
        return sum(a(u, t - lst[u])
                   for u in range(idx, len(lst)))
    return a(0, target)

print(check(200, (1, 2, 5, 10, 20, 50, 100, 200, 500)))

推荐阅读