python - 为什么三元迭代比递归慢 2 倍？

Question

为了解决我的问题，我需要将所有可能的长度为 N 的数组放在一起，包含 -1、0 和 1，然后通过某个函数运行它们以查看它们是否满足特定条件。

我已经实现了 2 种方法，一种是三元数方法，一种是递归。它们都返回正确的结果，都检查相同数量的数组，没有危险信号，除了在我的机器上，triadic 方法几乎慢了 2 倍。有什么理由会这样吗？ printIfTargetHit 是一个简单的数值函数，没有缓存或其他可以解释问题的复杂情况。

def triadicIteraction(signsQty):
    signs = [None for _ in range(signsQty)]
    comb = int(3**signsQty-1)
    while (comb >= 0):
        combCopy = comb
        for n in range(signsQty):
            signs[n] = 1-combCopy%3 # [0,1,2] -> [1,0,-1], correct range for signs
            combCopy = combCopy//3
        printIfTargetHit(signs)
        comb = comb - 1

def recursiveIteration(signsQty):
    def recursiveIterationInner(signs, newSign, currentOrder):
        if (currentOrder >= 0):
            signs[currentOrder] = newSign
        if currentOrder == (len(signs) - 1):
            printIfTargetHit(signs)
        else:
            recursiveIterationInner(signs,-1, currentOrder+1)
            recursiveIterationInner(signs, 0, currentOrder+1)
            recursiveIterationInner(signs, 1, currentOrder+1)
    recursiveIterationInner(signs = [None for _ in range(signsQty)], newSign = None, currentOrder = -1)

完整代码在 github 上，https://github.com/Yulia5/workspace/blob/master/P2/P3/PlusesMinuses1ToN.py ，我没有发布所有内容，因为我相信上面的示例是自给自足的。

性能输出，时间计算为 datetime.datetime.now() 之间的差异，第一种方法是直接的嵌入式循环。

Method name: <function embeddedLoopsFixed at 0x01D63D30>
Combination quantity : 16560
Combinations evaluated : 14348907
Time elapsed : 0:01:56.440000
Method name: <function recursiveIteration at 0x01D63DB0>
Combination quantity : 16560
Combinations evaluated : 14348907
Time elapsed : 0:02:20.526000
Method name: <function triadicIteraction at 0x01D63D70>
Combination quantity : 16560
Combinations evaluated : 14348907
Time elapsed : 0:04:12.297000

Answer 1

问题是你每次都在 triadicIteraction 中执行 O(n) 操作:

    for n in range(signsQty):
        signs[n] = 1-combCopy%3 # [0,1,2] -> [1,0,-1], correct range for signs
        combCopy = combCopy//3

要查看这一点，您可以使用标准库中的 profile 模块并实现函数，以便每个计算都在单独的函数中进行(此处名为 calSigns):

def triadicIteractionGranular(signsQty):
    signs = [None for _ in range(signsQty)]
    comb = int(3**signsQty-1)

    def calSigns(combCopy):
        for n in xrange(signsQty):
            signs[n] = 1-combCopy%3 # [0,1,2] -> [1,0,-1], correct range for signs
            combCopy = combCopy//3

    while (comb >= 0):
        calSigns(comb)
        printIfTargetHit(signs)
        comb = comb - 1

然后:

>> profile.run('runCombinationCheckingMethod(triadicIteractionGranular, [], {"signsQty" : 15})')
Method name: <function triadicIteractionGranular at 0x10f466848>
Combination quantity : 16560
Combinations evaluated : 14348907
Time elapsed : 0:02:34.560533
         43394489 function calls in 154.561 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000  154.561  154.561 <ipython-input-1-bf48bf6dbc36>:119(runCombinationCheckingMethod)
   264960    0.068    0.000    0.068    0.000 <ipython-input-1-bf48bf6dbc36>:18(onesZerosToChars)
    16560    0.355    0.000    0.488    0.000 <ipython-input-1-bf48bf6dbc36>:27(printEqualityAsString)
 14348907   66.392    0.000   66.392    0.000 <ipython-input-1-bf48bf6dbc36>:33(evaluate)
 14348907    8.279    0.000   75.159    0.000 <ipython-input-1-bf48bf6dbc36>:54(printIfTargetHit)
    16561    0.024    0.000    0.024    0.000 <ipython-input-1-bf48bf6dbc36>:7(combinationNumber)
        1   10.580   10.580  154.560  154.560 <ipython-input-26-037769fa8fac>:1(triadicIteractionGranular)

  **** Note this line ****
  14348907   68.822    0.000   68.822    0.000 <ipython-input-26-037769fa8fac>:5(calSigns)

        1    0.000    0.000  154.561  154.561 <string>:1(<module>)
        2    0.000    0.000    0.000    0.000 {built-in method now}
    16560    0.005    0.000    0.005    0.000 {len}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
    16560    0.017    0.000    0.017    0.000 {method 'join' of 'str' objects}
    16561    0.020    0.000    0.020    0.000 {range}

其他功能的配置文件看起来很相似，没有 calSign 的成本。

---

解决方案

有一种方法可以实现 triadicIteraction 而不会每次都产生 O(n) 成本:

def triadicIteractionFirstPrinciple(signsQty):
    signs = [-1 for _ in range(signsQty)]
    comb = int(3**signsQty-1)

    def addOne(idx=0):
        if signs[idx] < 1:
            signs[idx] += 1
        else:
            signs[idx] = -1
            addOne(idx+1)

    while (comb >= 0):
        printIfTargetHit(signs)
        if comb > 0: addOne()
        comb = comb - 1

这应该避免 O(n) 成本，并为您提供与其他实现相当的结果。

---

在我的系统上:

>> profile.run('runCombinationCheckingMethod(triadicIteractionFirstPrinciple, [], {"signsQty" : 15})')
Method name: <function triadicIteractionFirstPrinciple at 0x10f62e7d0>
Combination quantity : 16560
Combinations evaluated : 14348907
Time elapsed : 0:01:37.383544
         50568926 function calls (43394488 primitive calls) in 97.384 seconds