On Thu, Jul 11, 2013 at 1:47 AM, bas <[email protected]> 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. Removing
> 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 the
> 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 = [(2,2)] #heap of tuples (multiple, prime). start with 1 item, so no
> need for heapify
>
> #during loop
> smallest, prm = 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=2
yield 2
prime=[(2,2)] # Heap
while True:
smallest, prm = heappop(prime)
heappush(prime, (smallest+prm, prm))
while i<smallest:
yield i
heappush(prime, (i+i, i))
i+=1
if i==smallest: i+=1
gen=primes()
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. Thanks!
>> > 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 that
> it works correctly if for example a smallest factor appears twice in the
> list. I don't have time for it now, but it for sure can be simplified. The
> while loop, for example, can be replaced by an if, since it will never
> execute 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
--
http://mail.python.org/mailman/listinfo/python-list
