3
\$\begingroup\$

I implemented the Sieve of Erasthotenes recursively using filter and I was wondering how efficient this implementation is and wether a non-recursive implementation or something without filter would be better. If someone wants to get into micro-optimization etc. - that would be fun too I suppose :)

This is my code:

def sieve (iterable, container):
    if len(iterable) != 1:
        container.append(iterable [0])
        iterable = [item for item in iterable if item % iterable [0] != 0]
        print("Filter call:", iterable, container, '\n')
        return sieve(iterable, container)
    else: 
        container.append(iterable[0])
        print("Return container:", container)
        return container

An example I/O (with the print-Statements) would be:

#Input
lst = list(range(2, 20))
primes = []

print(sieve(lst, primes)

#Output
Filter call: [3, 5, 7, 9, 11, 13, 15, 17, 19] [2] 

Filter call: [5, 7, 11, 13, 17, 19] [2, 3] 

Filter call: [7, 11, 13, 17, 19] [2, 3, 5] 

Filter call: [11, 13, 17, 19] [2, 3, 5, 7] 

Filter call: [13, 17, 19] [2, 3, 5, 7, 11] 

Filter call: [17, 19] [2, 3, 5, 7, 11, 13] 

Filter call: [19] [2, 3, 5, 7, 11, 13, 17] 

Return container: [2, 3, 5, 7, 11, 13, 17, 19]

#Return
Out: [2, 3, 5, 7, 11, 13, 17, 19]
\$\endgroup\$
2
\$\begingroup\$

Algorithm

This is not quite the Sieve of Eratosthenes. The true sieve touches only the multiples of each prime, so it has complexity \$n \log \log n\$. Filtering copies the whole list repeatedly, which is equivalent to a different algorithm, trial division, with different complexity (probably \$n^2 / (\log n)^2\$). That's a dramatic difference, which led Melissa O'Neill to write a slightly famous academic rant about this.

But that's not a problem for an educational program. The rest of this review is about your implementation.

Recursing on each prime has depth \$\pi(n) \approx n / \log n\$, which will overflow the stack for any large \$n\$. Can you do it iteratively instead?

Names

iterable is a misleading name: the function uses len(iterable), but iterables don't necessarily support len. So it doesn't work on all iterables.

iterable is also an uninformative name: it doesn't say what the argument means. It isn't just any iterable, it's a list of candidate primes, so it could be called candidates.

Similarly, container isn't just any container, it's a list of primes, so it should be called primes. Also, sieve modifies it, which is unusual enough that it requires a comment, and it could even appear in the name: it could be called output_primes.

Interface

Modifying an argument is confusing and error-prone. Why not build a list and return it?

Why does the caller need to provide a list of candidates? Wouldn't it be simpler to just pass n and have sieve take care of building the candidates?

If the recursive function needs a different interface from the caller, you can use one function to do the recursion, and wrap it with another that presents a clean interface to the caller.

Innards

Repetition: container.append(iterable[0]) appears in both branches of the if. It could be moved before the if.

The program checks len(iterable) != 1, so what happens if len(iterable) == 0? Oops: it tries to use iterable[0] and crashes. It's generally safest to check for 0, not 1. This would also get rid of the repetition.

Optimization

Improving the algorithm will help a lot more than micro-optimizing. If you switch to the true Sieve of Eratosthenes and it still isn't fast enough, there are algorithmic improvements like the Sieve of Sundaram.

Before optimizing, measure performance! Optimization is hard and it's easy to get it wrong, so let measurements guide you.

Other

This function should have a docstring saying what it does: "Prime number sieve: Given a list of candidates, append the primes to output_primes."

Your question says the program uses filter, but it actually uses a list comprehension to do the same thing. This is not a problem with the program, just slightly confusing.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.