Path: csiph.com!usenet.pasdenom.info!weretis.net!feeder1.news.weretis.net!feeder.erje.net!eu.feeder.erje.net!xlned.com!feeder1.xlned.com!newsfeed.xs4all.nl!newsfeed2.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail
MIME-Version: 1.0
In-Reply-To: <51dd8560$0$9505$c3e8da3$5496439d@news.astraweb.com>
References: <mailman.4522.1373464867.3114.python-list@python.org> <51dd8560$0$9505$c3e8da3$5496439d@news.astraweb.com>
Date: Thu, 11 Jul 2013 02:52:31 +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
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.4538.1373475160.3114.python-list@python.org>
Lines: 67
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:50380

On Thu, Jul 11, 2013 at 2:01 AM, Steven D'Aprano
<steve+comp.lang.python@pearwood.info> wrote:
> On Thu, 11 Jul 2013 00:00:59 +1000, Chris Angelico wrote:
>> Thirdly, is there any sort of half-sane benchmark that I
>> can compare this code to? And finally, whose wheel did I reinvent here?
>> What name would this algorithm have?
>
> I can't directly answer that question, but I can make a shameless plug
> for this:
>
> https://pypi.python.org/pypi/pyprimes
>
> If your prime generator performs better than, or worse than, all of those
> in the above module, I may have to steal it from you :-)

Ha, that's what I was hoping for. My algorithm outperforms several of
yours! Look!

Rosuav: 0.10868923284942639
awful_primes: 16.55546780386893
naive_primes1: 2.6105180965737276
naive_primes2: 1.358270674066116
trial_division: 0.06926075800136644
turner: 0.5736550315752424
croft: 0.007141969160883832
sieve: 0.01786707528470899
cookbook: 0.014790147909859996
wheel: 0.015050236831779529

Okay, so I outperform only algorithms listed as toys... :| Here's
similar figures, going to a higher cutoff (I kept it low for the sake
of awful_primes) and using only the algos designed for real use:

Rosuav: 2.1318494389650082
croft: 0.11628042111497416
sieve: 0.26868582459502566
cookbook: 0.21551174800149164
wheel: 0.4761577239565362

I didn't seriously think that this would outperform mathematically
proven and efficient algorithms, it was just a toy. But at least now I
know: It's roughly 20 times slower than a leading algo. And that's
after the bas-suggested improvement of using a heap.

But hey. If you want the code, you're welcome to it - same with anyone
else. Here's the heap version as used in the above timings. MIT
license.

def primes():
	"""Generate an infinite series of prime numbers."""
	from heapq import heappush,heappop
	i=2
	yield 2
	prime=[(2,2)] # Heap
	while True:
		smallest, prm = heappop(prime)
		heappush(prime, (smallest+prm, prm))
		if i<smallest:
			yield i
			heappush(prime, (i+i, i))
			i+=1
		if i==smallest: i+=1
# ----

Enjoy!

ChrisA