Path: csiph.com!newsfeed.hal-mli.net!feeder3.hal-mli.net!newsfeed.hal-mli.net!feeder1.hal-mli.net!newsfeed.xs4all.nl!newsfeed3.news.xs4all.nl!xs4all!news2.euro.net!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
MIME-Version: 1.0
In-Reply-To: <ff09d214-1962-4500-a2a3-483872ce2cb9@googlegroups.com>
References: <mailman.4522.1373464867.3114.python-list@python.org> <15167633-b6e7-46cc-a043-8dfe8aaad11e@googlegroups.com> <mailman.4525.1373469147.3114.python-list@python.org> <ff09d214-1962-4500-a2a3-483872ce2cb9@googlegroups.com>
Date: Thu, 11 Jul 2013 02:15:06 +1000
Subject: Re: Prime number generator
From: Chris Angelico <rosuav@gmail.com>
To: python-list@python.org
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.4534.1373472909.3114.python-list@python.org>
Lines: 84
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:50376

On Thu, Jul 11, 2013 at 1:47 AM, bas <blswinkels@gmail.com> wrote:
> On Wednesday, July 10, 2013 5:12:19 PM UTC+2, Chris Angelico wrote:
>> Well, that does answer the question. Unfortunately the use of lambda
>> there has a severe performance cost [ ...]
> If you care about speed, you might want to check the heapq module. Removi=
ng the smallest item and inserting a new item in a heap both cost O(log(N))=
 time, while finding the minimum in a dictionary requires iterating over th=
e whole dictionary, which cost O(N) time.

Ehh, speed isn't the ultimate. I was just trying to avoid something
that worked out ridiculously slow (a Python function call IS quite
slow). I haven't profiled the code to find out where the bulk of the
time is spent, but switching in the lambda-based version doubled total
run time, so I didn't like it :)

> (untested)
> #before loop
> from heapq import *
> primes =3D [(2,2)] #heap of tuples (multiple, prime). start with 1 item, =
so no need for heapify
>
> #during loop
> smallest, prm =3D heappop(primes)
> heappush(primes, (smallest+prm, prm))
>
> #when new prime found
> heappush(primes, (i+i, i))

Ahh, that's the bit I should have thought of! Of course.

My original thought experiment had involved basically a really long
list, like the classic Sieve but getting longer as time moves on, with
composites replaced by None and primes with their next-markers, which
I then collapsed to a dict. Always I was thinking in terms of indexing
with the prime to get its next composite. Here's the code involving
heapq:

# -- start --
def primes():
	"""Generate an infinite series of prime numbers."""
	from heapq import heappush,heappop
	i=3D2
	yield 2
	prime=3D[(2,2)] # Heap
	while True:
		smallest, prm =3D heappop(prime)
		heappush(prime, (smallest+prm, prm))
		while i<smallest:
			yield i
			heappush(prime, (i+i, i))
			i+=3D1
		if i=3D=3Dsmallest: i+=3D1

gen=3Dprimes()
print([next(gen) for i in range(10)])
for i in range(1000):
	next(gen) # Star Trek?
print("The next prime number is:",next(gen))
# -- end --

And that's significantly shorter, clearer, AND faster than the original. Th=
anks!

>> > Still trying to figure out your algorithm ...
>> It's pretty simple.  [...]
> I understand what you are trying, but it is not immediately clear to me t=
hat it works correctly if for example a smallest factor appears twice in th=
e list. I don't have time for it now, but it for sure can be simplified. Th=
e while loop, for example, can be replaced by an if, since it will never ex=
ecute more than once (since if i is prime > 2, i+1 will be divisible by 2)

Ah, good point. Again, I originally was starting from 1, so the while
loop was necessary to catch 2 and 3 in the first run. When I changed
it to start at 2 and explicitly yield it first, I didn't notice to
change that.

It works correctly with the smallest multiple appearing twice because
it won't yield primes until the smallest value is higher than the
current next-prime. So when it's just yielded 11, for instance, both
the 2 and 3 slots hold 12; advancing one of those does nothing,
advancing the other allows the bottom loop to notice that 13 is now
lower than the minimum value (which will then be 14).

ChrisA