Re: Prime number generator

Path	csiph.com!usenet.pasdenom.info!weretis.net!feeder1.news.weretis.net!feeder.erje.net!eu.feeder.erje.net!xlned.com!feeder3.xlned.com!newsfeed.xs4all.nl!newsfeed3.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail
Return-Path	<ian.g.kelly@gmail.com>
X-Original-To	python-list@python.org
Delivered-To	python-list@mail.python.org
X-Spam-Status	OK 0.010
X-Spam-Evidence	'H': 0.98; 'S': 0.00; 'pop': 0.05; 'element': 0.07; 'smallest': 0.07; 'subject:number': 0.09; 'dictionary,': 0.16; 'element.': 0.16; 'heap': 0.16; 'heapq': 0.16; 'inserting': 0.16; 'iterating': 0.16; 'likewise': 0.16; 'subject:Prime': 0.16; 'subject:generator': 0.16; 'swaps': 0.16; 'pushed': 0.16; 'wrote:': 0.18; 'wed,': 0.18; 'dependent': 0.19; '>>>': 0.22; 'performing': 0.26; 'push': 0.26; 'header:In-Reply-To:1': 0.27; 'am,': 0.29; 'returned': 0.30; 'message-id:@mail.gmail.com': 0.30; 'getting': 0.31; "i'd": 0.34; 'problem': 0.35; 'but': 0.35; 'received:google.com': 0.35; 'module.': 0.36; 'list': 0.37; 'implement': 0.38; 'minimum': 0.38; 'saves': 0.38; 'to:addr :python-list': 0.38; 'to:addr:python.org': 0.39; 'removing': 0.60; 'new': 0.61; 'here': 0.66; 'jul': 0.74; 'actually,': 0.84; 'hood': 0.84; 'imagine': 0.93; '2013': 0.98
DKIM-Signature	v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :content-type:content-transfer-encoding; bh=EG2Vd5my8J2oVnJVroABw+BxGQes6VvNNYdnnq9bE8Q=; b=cKPnAzf6c7IoHHChU9vJzpU5v8GVBNixPwfN9HR6azS3wyuw2E9UZe1QK7CQJXw2qB kMr/BAKE8ZMUxgkDv0nPDFYEetuOPzvfCR25KzqNS8446rxcaXsd4uag/gpYSoD1l37f MV49u6FBkEMfGjfuSgGcP91KogfXRl7zJNZPTQCPq0TBbup3V0XIZBr1VHOVEsherxXS NegGeUa1AorIBala7R+HblrGgspUaOe4WIjmBZ39V+aLyW7U45VVR1p77P/ohRZmg7kX hQeloyxdyj2bg9t1Zoh5QRTbmuNR43X45DD+yUtf0IE1XJ+meqYE4BHtlEZY6YDnSZ7E icIw==
X-Received	by 10.68.28.232 with SMTP id e8mr33266522pbh.94.1373482616963; Wed, 10 Jul 2013 11:56:56 -0700 (PDT)
MIME-Version	1.0
In-Reply-To	<CAN1F8qXajvvpUjFnMNRzQiBbvrPUz4b9QXck1RRNhWJYxkQDhw@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> <CAN1F8qXajvvpUjFnMNRzQiBbvrPUz4b9QXck1RRNhWJYxkQDhw@mail.gmail.com>
From	Ian Kelly <ian.g.kelly@gmail.com>
Date	Wed, 10 Jul 2013 12:56:16 -0600
Subject	Re: Prime number generator
To	Python <python-list@python.org>
Content-Type	text/plain; charset=ISO-8859-1
Content-Transfer-Encoding	quoted-printable
X-BeenThere	python-list@python.org
X-Mailman-Version	2.1.15
Precedence	list
List-Id	General discussion list for the Python programming language <python-list.python.org>
List-Unsubscribe	<http://mail.python.org/mailman/options/python-list>, <mailto:python-list-request@python.org?subject=unsubscribe>
List-Archive	<http://mail.python.org/pipermail/python-list/>
List-Post	<mailto:python-list@python.org>
List-Help	<mailto:python-list-request@python.org?subject=help>
List-Subscribe	<http://mail.python.org/mailman/listinfo/python-list>, <mailto:python-list-request@python.org?subject=subscribe>
Newsgroups	comp.lang.python
Message-ID	<mailman.4545.1373482626.3114.python-list@python.org> (permalink)
Lines	20
NNTP-Posting-Host	2001:888:2000:d::a6
X-Trace	1373482626 news.xs4all.nl 15968 [2001:888:2000:d::a6]:34642
X-Complaints-To	abuse@xs4all.nl
Xref	csiph.com comp.lang.python:50388

Show key headers only | View raw

On Wed, Jul 10, 2013 at 11:47 AM, Joshua Landau <joshua@landau.ws> wrote:
>>> 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 :/.

It shouldn't.  You can implement push by appending the new item and
then getting it into the right place by performing O(log n) swaps.
Likewise for pop, you can update the heap with O(log n) swaps and then
removing the tail element.  Appending or removing the tail element of
a list is amortized O(1).

> PS: It's faster to use heapreplace(...) than
> heappop(...);heappush(...) but it only saves a few %.

The problem with heapreplace here is that the value to be pushed
is dependent on the value returned by pop.

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