python - 组合和的记忆化与非记忆化时间复杂度分析

Question

我试图理解为什么使用 lru_cache 来解决这个问题会导致代码性能下降。

The question本质上是返回所有加起来达到某个目标的组合。

我正在使用 lru_cache 装饰器进行内存(docs)，这是我的解决方案:

from functools import lru_cache

def combinationSum(candidates, target):
    return dfs(tuple(candidates), 0, target)

@lru_cache(maxsize=None)
def dfs(candidates, i, target):
    if target < 0:
        return []

    if target == 0:
        return [[]]

    if i == len(candidates):
        return []

    final_results = []
    for j in range(i, len(candidates)):

        results = dfs(candidates, j, target - candidates[j])

        for x in results:
            final_results.append([candidates[j]] + x)

    return final_results

似乎当 lru_cache 装饰器被注释掉时，该算法的运行速度提高了近 50%。这似乎有点违反直觉，因为我认为解决方案的时间复杂度应该降低，即使增加了从内存中检索结果的函数调用的开销。

对于内存解决方案，我认为时间复杂度应该是 O(n^2*k*2^n) 其中 n 是数组的长度， k 是从 0 到 target 范围内的所有数字。

这是我的分析(需要一点帮助来验证):

time complexity 
= possible states for memoization x work done at each step
= (n * k) * (n * maximum size of results)
= n * k * n * 2^n

我在如何分析递归解决方案的时间复杂度方面还缺少一些知识，我可以在这方面寻求一些帮助!

编辑:

我使用 range(1, 10000) 作为测试输入，这里是基准:

# with lru_cache
$ time python3 combination_sum.py
CacheInfo(hits=59984, misses=49996, maxsize=None, currsize=49996)

real    0m4.031s
user    0m3.996s
sys     0m0.024s

# without lru_cache
$ time python3 combination_sum.py

real    0m0.073s
user    0m0.060s
sys     0m0.010s

Answer 1

您没有给出两个 参数，它们都很重要。通过选择特定 对，我可以使任一版本都比另一个版本快得多。如果您将 range(1, 10000) 作为 candidates 传递，那么每次缓存查找都必须(除其他外)进行 9999 次比较，以确定候选总是相同 - 这是巨大的开销。尝试，例如，

combinationSum(range(1, 1000), 45) # not ten thousand, just one thousand

对于缓存版本更快的情况。之后:

>>> dfs.cache_info()
CacheInfo(hits=930864, misses=44956, maxsize=None, currsize=44956)

如果您不考虑执行缓存查找的费用，“分析”是徒劳的，而且您显然正在尝试缓存查找极其昂贵的情况。字典查找是预期情况 O(1)，但隐藏常数因子可以任意大，具体取决于相等性测试的成本(以及涉及 N 的键) -元素元组，建立相等性至少需要 N 次比较)。

这应该提出一项重大改进:将 candidates 排除在参数列表之外。它是不变的，所以真的没有必要传递它。然后缓存只需要存储快速比较的(i, target) 对。

编辑:实际变化

这是未通过 candidates 的代码的另一个版本。对于

combinationSum(range(1, 10000), 45)

它在我的盒子上至少快了 50 倍。还有一个重大变化:当 target 减少到零以下时，不要进行递归调用。大量缓存条目记录了 (j, negative_integer) 参数的空列表结果。在上述情况下，此更改将最终缓存大小从 449956 减少到 1036 - 并将命中数从 9444864 减少到 6853。

def combinationSum(candidates, target):

    @lru_cache(maxsize=None)
    def dfs(i, target):
        if target == 0:
            return [[]]
        assert target > 0
        if i == n:
            return []
        final_results = []
        for j in range(i, n):
            cand = candidates[j]
            if cand <= target:
                results = dfs(j, target - cand)
                for x in results:
                    final_results.append([cand] + x)
        return final_results

    n = len(candidates)
    result = dfs(0, target)
    print(dfs.cache_info())
    return result