two ways to extend a list with drastically different performance
This is spin-off from my previous question, where we have a function:
def divbelow_5(n,B):
div = [1]
for p, e in factor(n):
pn = 1
prev = div.copy()
for i in range(e):
pn *= p
div.extend(r for d in prev if (r := d * pn) <= B)
return len(div)
I've decided to optimize and beautify it a bit into:
def divbelow_6(n,B):
div = [1]
for p, e in factor(n):
L = len(div)
div.extend(r for i in range(L) for k in (1..e) if (r := div[i] * p^k) <= B)
return len(div)
I'd expect divbelow_6
to have comparable (if not better) performance than divbelow_5
, but the reality puzzled me a lot:
sage: %time divbelow_5(47987366728745697656468743117440000, 61448226992991993)
CPU times: user 2.22 s, sys: 240 ms, total: 2.46 s
Wall time: 2.46 s
10074213
sage: %time divbelow_6(47987366728745697656468743117440000, 61448226992991993)
CPU times: user 1min 39s, sys: 326 ms, total: 1min 39s
Wall time: 1min 39s
10074213
Why divbelow_6
is so much slower than divbelow_5
?
It seems that
(1..e)
is much slower thanrange(1, e+1)
(although a version withrange
is still slower thandivbelow_5
).Wow! It's indeed very much slower. Perhaps, this needs to be reported as a bug.