two ways to extend a list with drastically different performance

asked 2023-03-05 15:05:32 +0100

Max Alekseyev gravatar image

updated 2023-03-05 15:06:48 +0100

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 ?

edit retag flag offensive close merge delete

Comments

1

It seems that (1..e) is much slower than range(1, e+1) (although a version with range is still slower than divbelow_5).

John Palmieri gravatar imageJohn Palmieri ( 2023-03-05 20:25:02 +0100 )edit

Wow! It's indeed very much slower. Perhaps, this needs to be reported as a bug.

Max Alekseyev gravatar imageMax Alekseyev ( 2023-03-08 02:41:39 +0100 )edit