Why is my code slower when I try to memoize?

Question

I have a function that lists the prime numbers smaller than N:

def ListPrimes(N):
    list = [2]
    for n in range(3, N, 2):
        for i in range(3, int(sqrt(n)+1)):
            if n % i == 0:
                break
        else:
            list.append(n)
    return list

I tried to make it faster, so I changed one line to the following:

def ListPrimesFaster(N):
   list = [2]
   for n in range(3, N, 2):
        for i in list:
            if n % i == 0:
                break
        else:
            list.append(n)
    return list

I was surprised that the second version is at least 5 times slower, given that it is identical to the first except that the variable i has to iterate through a shorter list.

I am trying to find a faster way to list prime numbers smaller than some N.

@barakmanos, the indentation is correct and the second snippet functions correctly, albiet slower. — Kevin W., Feb 22 '17 at 19:34
@KevinW.: Well, I must be missing something here. What `if` does this `else` correspond to? — barak manos, Feb 22 '17 at 19:36
@barakmanos http://stackoverflow.com/questions/9979970/why-does-python-use-else-after-for-and-while-loops — Barmar, Feb 22 '17 at 19:39
@Barmar: Thanks. I am embarrassed to say that I've never seen this construct before (nor could I imagine that the "pedantic" Python standard would even allow it). At least I found some comfort in the opening statement of the accepted answer on that link - "It's a strange construct even to seasoned Python coders". Anyhow, it's good to learn new tricks I suppose (though I doubt that I'd ever use it due to the ambiguity IMO). — barak manos, Feb 22 '17 at 19:42
Put `print` statements in both loops, you'll see that `ListPrimesFaster()` has more iterations of the inner loop, not fewer — Barmar, Feb 22 '17 at 19:47

score 1 · Accepted Answer · answered Feb 22 '17 at 20:03

ListPrimesFaster() doesn't search through a shorter list, because it includes elements in list that are higher than sqrt(n). The size of list grows faster than sqrt(n), and starting the range at 3 saves a few steps as well. ListPrimes(100) performs 139 n % i == 0 tests, while ListPrimesFaster(100) does 362. When N is 500, the test counts are 1616 versus 4933.

BTW, in ListPrimes(), the inner loop only needs to test odd factors, since n is always odd, so you could change it to:

for i in range(3, int(sqrt(n)+1), 2):

This simple change drops the number of tests to 87 for N = 100, and 907 for N = 500.

Yes, thank you. That was silly of me I can't believe I missed it! I added a condition to exit the loop once i reach a number larger than sqrt(n) and it runs much faster now. — J. Zeitouni, Feb 22 '17 at 20:37

Why is my code slower when I try to memoize?

1 Answers1