I noticed a strange performance hit from a minor refactoring that replaced a loop with a call to the builtin max
inside a recursive function.
Here's the simplest reproduction I could produce:
import time
def f1(n):
if n <= 1:
return 1
best = 0
for k in (1, 2):
current = f1(n-k)*n
if current > best:
best = current
return best
def f2(n):
if n <= 1:
return 1
return max(f2(n-k)*n for k in (1, 2))
t = time.perf_counter()
result1 = f1(30)
print('loop:', time.perf_counter() - t) # 0.45 sec
t = time.perf_counter()
result2 = f2(30)
print('max:', time.perf_counter() - t) # 1.02 sec
assert result1 == result2
Both f1
and f2
calculate factorial using the standard recursion but with an unnecessary maximization added in (just so I get to use max
in a recursion while still keeping the recursion simple):
# pseudocode
factorial(0) = 1
factorial(1) = 1
factorial(n) = max(factorial(n-1)*n, factorial(n-2)*n)
It's implemented without memoization, so there's an exponential number of calls.
The implementation with max(iterable)
is more than twice slower than the one with the loop.
Oddly, a direct comparison of (edit: never mind, see @TimPeters answer). Also, if I use max
vs loop did not demonstrate the effectmax(a, b)
instead of max(iterable)
the performance mismatch disappears.
Posting this as "an answer" because useful formatting is impossible in comments:
$ python -m timeit "max(1, 2)" # straight
10000000 loops, best of 3: 0.148 usec per loop
$ python -m timeit "max([i for i in (1, 2)])" # list comp
1000000 loops, best of 3: 0.328 usec per loop
$ python -m timeit "max(i for i in (1, 2))" # genexp
1000000 loops, best of 3: 0.402 usec per loop
Which shows that the recursion is a red herring. It's generally true, as these results show, that a genexp is slower than a listcomp, which is in turn slower than using neither. Since your code is doing more than just a max, the timing differences aren't as extreme - but since it's doing little more than just a max, the speed of the max part is nevertheless highly significant.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With