Path: csiph.com!newsfeed.hal-mli.net!feeder3.hal-mli.net!newsfeed.hal-mli.net!feeder1.hal-mli.net!newsfeed.xs4all.nl!newsfeed4.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail
MIME-Version: 1.0
Sender: joshua.landau.ws@gmail.com
In-Reply-To: <CAPTjJmqY6_gaGqvRSYzccWU1EjHPFxYkWWXHhPcwE+iZoDW2zg@mail.gmail.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> <CAPTjJmqY6_gaGqvRSYzccWU1EjHPFxYkWWXHhPcwE+iZoDW2zg@mail.gmail.com>
From: Joshua Landau <joshua@landau.ws>
Date: Wed, 10 Jul 2013 18:47:11 +0100
Subject: Re: Prime number generator
To: Chris Angelico <rosuav@gmail.com>
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Cc: python-list <python-list@python.org>
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.4541.1373478479.3114.python-list@python.org>
Lines: 78
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:50384

On 10 July 2013 17:15, Chris Angelico <rosuav@gmail.com> wrote:
> 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. Remov=
ing 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 t=
he 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 =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. =
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 %.