Why is the process iteration 2 times slower than recursion?

Question

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

I implemented 2 methods, process numbers method and recursion. They both return the correct results, both check the same number of arrays, no red flags, in addition, on my machine the triad method is almost 2 times slower. Is there a reason why this should be so? printIfTargetHit is a simple numerical function, not caching or other complications that might explain the problem.

 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 on github, https://github.com/Yulia5/workspace/blob/master/P2/P3/PlusesMinuses1ToN.py , I did not publish all this because I believe that the above example is self-sufficient.

Performance, timing, calculated as the difference between datetime.datetime.now() , the first method is simple built-in 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 perform O(n) operation every 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 implement such a function that each calculation is performed in a separate function (here 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 

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} 

Profiles from another function look the same, without the cost of calSign .

---

Decision

There is a way to implement triadicIteraction without losing the cost of 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 

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

---

In 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