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

Question

为了解决我的问题,我需要将所有可能的长度为N的数组放在一起,包含-1,0和1,并通过某些函数运行它们以查看它们是否符合某个标准.

我已经实现了2个方法,一个三元数方法和一个递归.它们都返回正确的结果,都检查相同数量的数组,没有红旗除外,在我的机器上,三元方法几乎慢了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()'s 之间的差异,第一种方法是简单的嵌入式循环.

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

问题是你O(n)每次都在triadicIteraction这里做一个操作：

    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