Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #50384

Re: Prime number generator

Show key headers only | View raw

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. 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 %.

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Prime number generator Chris Angelico <rosuav@gmail.com> - 2013-07-11 00:00 +1000
  Re: Prime number generator Bas <wegwerp@gmail.com> - 2013-07-10 07:35 -0700
    Re: Prime number generator Chris Angelico <rosuav@gmail.com> - 2013-07-11 01:12 +1000
      Re: Prime number generator bas <blswinkels@gmail.com> - 2013-07-10 08:47 -0700
        Re: Prime number generator Chris Angelico <rosuav@gmail.com> - 2013-07-11 02:15 +1000
        Re: Prime number generator Joshua Landau <joshua@landau.ws> - 2013-07-10 18:47 +0100
        Re: Prime number generator Ian Kelly <ian.g.kelly@gmail.com> - 2013-07-10 12:56 -0600
        Re: Prime number generator Joshua Landau <joshua@landau.ws> - 2013-07-10 20:06 +0100
      Re: Prime number generator bryanjugglercryptographer@yahoo.com - 2013-07-30 21:57 -0700
  Re: Prime number generator Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-07-10 16:01 +0000
    Re: Prime number generator Chris Angelico <rosuav@gmail.com> - 2013-07-11 02:52 +1000
  Re: Prime number generator albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-07-30 10:58 +0000
    Re: Prime number generator Ian Kelly <ian.g.kelly@gmail.com> - 2013-07-30 11:33 -0600

csiph-web