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

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. Remo=
ving 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.