3
\$\begingroup\$

I'm trying to get a better grasp on generators in Python because I don't use them enough (I think generators are cool). To do so I wrote a generator for prime numbers:

def primes():
    x = 2
    while True:
        for y in xrange(2, x/2 + 1):
            if x % y == 0:
                break
        else:
            yield x
        x = x + 1

This works as expected but if I use list comprehension to create a list of primes using this generator it's really slow when compared to sieve function that generates the same list:

[prime.next() for i in xrange(1000)] # exectues in 0.212 sec, sieve in 0.001 sec

I'm assuming that this is not the intended purpose of a generator, but I thought I would see if anyone can think of a way to make this faster.

\$\endgroup\$
  • 1
    \$\begingroup\$ I can't come up with a proper answer at the moment but you should look into using memoization and a different algorithm here. \$\endgroup\$ – Jeff Mercado Dec 10 '11 at 20:05
6
\$\begingroup\$

Stylistically, using itertools.count() rather than implementing your own counter would be a bit cleaner.

I also prefer using the any() over a generator rather than an explicit for loop with a break and else. I think it's easier to follow.

Algorithmically, the sieve has a big advantage because it uses the previously calculated primes to make checking the next prime faster. You don't need to check every number for divisions, just the primes. You could do something like:

past_primes = []
for x in itertools.count(2):
    if not any(x % prime == 0 for prime in past_primes):
        past_primes.append(x)
        yield x

Performing the division will still be more expensive than what the sieve has to do. You could implement the entire sieve algorithm in a generator. But I'm not sure what purpose that would serve.

Generally, generators work nicely when you don't have to maintain a lot of state for each value generated. But that's not the case for primes.

\$\endgroup\$
  • \$\begingroup\$ It's not really necessary to test divisibility by all past primes, only by ones up to sqrt(x). \$\endgroup\$ – UncleBens Dec 17 '11 at 17:37
2
\$\begingroup\$

I prefer using set instead of list in this case:

past_primes = set()
for x in itertools.count(2):
    if not any(x % prime == 0 for prime in past_primes):
        past_primes.add(x)
        yield x

Sets have better time complexity 0(1) vs O(n) of lists http://wiki.python.org/moin/TimeComplexity

\$\endgroup\$
  • \$\begingroup\$ Nope. What's being done here is iteration which you'll see is O(n) for both lists and sets. Lists have lower overhead and thus will be more efficient here. \$\endgroup\$ – Winston Ewert Dec 12 '11 at 16:49

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.