On 10 July 2013 17:15, Chris Angelico <ros...@gmail.com> wrote:
> On Thu, Jul 11, 2013 at 1:47 AM, bas <blswink...@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. 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.
Actually, because it's a list under the hood I'd imagine push and pop
still take 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!
AFAICT, that's exactly my code but using a less-efficient storage
medium and a *much* more efficient sorting mechanism. It'd be
interesting what could happen if heapq didn't reject blists -- they
have better efficiency for changing list sizes (which this code does a
lot of).
Thanks for the heads-up on heapq, by the way -- it's new to me and a
blimmin' good idea.
PS: It's faster to use heapreplace(...) than
heappop(...);heappush(...) but it only saves a few %.
--
http://mail.python.org/mailman/listinfo/python-list
