0
\$\begingroup\$

I've written a short implementation of the Eratosthenes' sieve.

def sieve(n):
    l = list(range(2, n + 1))
    out = []
    while len(l) > 0:
        out.append(l[0])
        l = list(filter(lambda n: n % l[0], l))
    return out

Is it lacking in efficiency? Are there any improvements or changes you would make?

\$\endgroup\$
5
\$\begingroup\$

Yes, the implementation is short. However, its efficiency is suspect. That's due to:

  1. Reassembling list every iteration
  2. Testing every remaining member of list using % operator

The beauty of Eratosthenes' sieve is that it shouldn't need any division (including %). With an array of values, we simply march along it in steps of n striking out members - that requires only addition, which is one of the cheapest operations in a digital computer. (There's an optimisation that also requires multiplying a number by itself; that's only used because it's faster than the equivalent additions).

Removing the empty cells at every iteration prevents us from accessing every nth element in this way, as well as imposing its own overheads (for a start, we'll need lots of extra memory when building the new list from the old).

\$\endgroup\$
  • 1
    \$\begingroup\$ Gave +1 mainly for quote: The beauty of Eratosthenes' sieve is that it shouldn't need any division. \$\endgroup\$ – Rick Davin Dec 4 '18 at 14:00
4
\$\begingroup\$

First of all first statement may be simplified to

 l = range(2, n + 1)

since range objects support indexing, so creating list from it will cause performance issues with no gain. Also it is less noisy to test lists for emptyness with

while l:
    ...

Wherever you are dealing with lists it may become faster (or at least, less memory consuming) by making calculations "lazy" using iterables/iterators/generators. So your function may be rewritten like

def sieve_2(n):
    numbers = iter(range(2, n + 1))

    def to_is_dividable_by(divisor):
        return lambda dividend: dividend % divisor

    while True:
        try:
            prime = next(numbers)
        except StopIteration:
            return
        yield prime
        numbers = filter(to_is_dividable_by(prime), numbers)

Note that we are creating predicate on each step since filter creates iterator object and if we will use some sort of partial application of prime as divisor to predicate like before:

l = filter(lambda n: n % prime, l)

this will lead to undesired behavior since prime will be modified on each step and all of applied lambda functions will change accordingly and have the same prime argument due to late binding (more info can be found here).

Test

On my laptop with Windows 10 in Python 3.6.5 gives

>>> from timeit import repeat
>>> min(repeat('sieve(10000)', 'from __main__ import sieve', number=10, repeat=7))
1.198557400000027
>>> min(repeat('list(sieve_2(10000))', 'from __main__ import sieve_2', number=10, repeat=7))
0.9349597000000358

Better, but still not so great, so we probably should review our algorithm for further improvements.

Searching on StackOverflow will lead us to this answer using which we have

>>> min(repeat('rwh_primes1v1(10000)', 'from __main__ import rwh_primes1v1', number=10, repeat=7))
0.003475800000160234
>>> min(repeat('rwh_primes1v2(10000)', 'from __main__ import rwh_primes1v2', number=10, repeat=7))
0.0025113000001510954
\$\endgroup\$
1
\$\begingroup\$

First of all, you have a while loop, which is slower than a for loop, and you have to check the length of l on every iteration - this wastes time. But that's nothing compared to this line here: l = list(filter(lambda n: n % l[0], l)) where you're creating a new list, a new function and then applying it to filter the list on each iteration. It's definitely lacking efficiency.

This should be faster:

def find_primes(to_n):
    primes = []
    sieve = [0 for n in range(to_n)]
    for n in range(2, to_n):
        if sieve[n] == 0:
            primes.append(n)
            for n_multiple in range(n, to_n, n):
                sieve[n_multiple] = 1
    return primes

Why? Because it's pretty much the exact implementation of Sieve of Eratosthenes; it iteratively marks the multiples of prime (second for loop) numbers as composites (by giving them a value of 1 in list sieve). Your version just adds some unnecessary steps at the cost of making it slightly shorter.

\$\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.