On Thu, Jul 11, 2013 at 2:01 AM, Steven D'Aprano
<steve+comp.lang.pyt...@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
--
http://mail.python.org/mailman/listinfo/python-list
