Revision history [back]

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 ?

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 ?