Why is triadic iteration 2 times slower than the recursion?

Question

To solve my problem, I need to put together all possible arrays of length N, containing -1, 0 and 1, and run them through some function to see whether they meet a certain criterion.

I have implemented 2 methods, a triadic numbers method and a recursion. They both return correct results, both check the same number of arrays, no red flags except that, on my machine, triadic method is almost 2 times slower. Is there any reason why this should be the case? printIfTargetHit is a simple numerical function, no caching or other complications that could explain the issue.

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)

Full code is on github, https://github.com/Yulia5/workspace/blob/master/P2/P3/PlusesMinuses1ToN.py, I did not post all of it because I believe the example above is self-sufficient.

Performance output, timings computed as the difference between datetime.datetime.now()'s, first method is straightforward embedded loops.

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

The problem is that you are doing an O(n) operation each time in triadicIteraction here:

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

To see this, you can use the profile module from the standard library and implementing the function such that each calculation happens in a separate function (named calSigns here):

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

Then:

>> 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}

The profiles from other function looks similar, without the cost of calSign.

---

Solution

There is a way of implementing the triadicIteraction without incurring that O(n) cost each time:

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

This should avoid the O(n) cost and give you results comparable to the other implementations.

---

On my system:

>> 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