Re: How to remove item from heap efficiently?

Path	csiph.com!fu-berlin.de!uni-berlin.de!not-for-mail
From	"Sven R. Kunze" <srkunze@mail.de>
Newsgroups	comp.lang.python
Subject	Re: How to remove item from heap efficiently?
Date	Wed, 13 Jan 2016 20:08:21 +0100
Lines	25
Message-ID	<mailman.114.1452712114.13488.python-list@python.org> (permalink)
References	<568EEC40.7070807@mail.de> <CACs7g=Bjccja67M3t4yL+07vO8iAcOB-dF5p2PgqqBwjFmbh=w@mail.gmail.com> <568FE797.6090808@mail.de> <CACs7g=CE7y-aXSdWbN7Fk0J4O4aRwAH5ad7UR1Jhdf9EpNFnug@mail.gmail.com> <5692A795.3070904@mail.de> <CACs7g=AuW8UTVS+SRM-bG=-Ne18W5VLt2CfTDjS0i1cH2qwtpw@mail.gmail.com> <FF3CA092-4D74-4C25-8C7A-C20D54C69657@gmail.com> <5695276A.2020101@mail.de> <7A7E26D9-01E5-4D77-92B4-3491D86E1EA8@gmail.com>
Mime-Version	1.0
Content-Type	text/plain; charset=windows-1252; format=flowed
Content-Transfer-Encoding	7bit
X-Trace	news.uni-berlin.de JJPrqT9juCkVbulkQKYtlQpMYJ5oPVse9obubro7pRfw==
Return-Path	<srkunze@mail.de>
X-Original-To	python-list@python.org
Delivered-To	python-list@mail.python.org
X-Spam-Status	OK 0.002
X-Spam-Evidence	'H': 1.00; 'S': 0.00; 'open-source': 0.04; 'pypi': 0.07; 'so?': 0.07; 'wrapper': 0.07; 'cc:addr:python-list': 0.09; 'subject:How': 0.09; 'assumed': 0.09; 'dict': 0.09; 'simplified': 0.09; 'underlying': 0.09; 'jan': 0.11; 'missed': 0.15; '_heapq': 0.16; 'heap': 0.16; 'heapq': 0.16; 'received:io': 0.16; 'received:psf.io': 0.16; 'somehow,': 0.16; 'subject:item': 0.16; 'subject:remove': 0.16; 'wrote:': 0.16; 'looked': 0.16; 'cc:addr:python.org': 0.20; 'issue.': 0.20; 'cc:21': 0.22; '(by': 0.22; 'cc:no real name:20': 0.22; 'am,': 0.23; 'code.': 0.23; "haven't": 0.24; 'cc:addr:gmail.com': 0.24; 'header:In- Reply-To:1': 0.24; "i've": 0.25; 'header:User-Agent:1': 0.26; 'least': 0.27; 'said,': 0.27; 'interface': 0.29; '"remove': 0.29; 'concern': 0.29; 'code': 0.30; 'another': 0.32; 'lets': 0.33; "i'll": 0.33; 'this?': 0.34; 'received:10.0': 0.34; 'so,': 0.35; 'best,': 0.35; 'could': 0.35; 'unknown': 0.35; 'asking': 0.35; 'item': 0.35; 'but': 0.36; 'subject:?': 0.36; 'subject:: ': 0.37; 'received:10': 0.37; 'really': 0.37; 'thanks': 0.37; '12,': 0.37; 'missing': 0.37; 'thought': 0.37; 'subject:from': 0.39; 'still': 0.40; 'received:de': 0.40; 'your': 0.60; 'skip:u 10': 0.61; 'replying': 0.61; 'here.': 0.62; 'charset:windows-1252': 0.62; 'skip:n 10': 0.62; 'it!': 0.64; 'hand': 0.82; 'coupled': 0.84; 'researching': 0.84; 'adopt': 0.91; 'different.': 0.91; 'maybe,': 0.91
DKIM-Signature	v=1; a=rsa-sha256; c=relaxed/simple; d=mail.de; s=mail201212; t=1452712105; bh=HsWpX3sW3Bkts0ckUNjEZLOLVO6CZcQdp5xrSunxsV0=; h=Subject:To:References:Cc:From:Date:In-Reply-To:From; b=HvM6pkyVuGMt0igzfbF9qu25cr8YS+JvOYG3MpJQy3cV5SBCykZJoGIOMrv1fyT8z a8L5b8gO8qFoTKfGpJ6QzfI/7xaHGgdX15RbkCa3hXBMO+JTZWsdkyfZHJfFObRnva 6oYFYzupHDwTlNQIpfJVkJcgjU33ZdGsYE0y8pMY=
User-Agent	Mozilla/5.0 (X11; Linux x86_64; rv:38.0) Gecko/20100101 Thunderbird/38.4.0
In-Reply-To	<7A7E26D9-01E5-4D77-92B4-3491D86E1EA8@gmail.com>
X-purgate	clean
X-purgate	This mail is considered clean (visit http://www.eleven.de for further information)
X-purgate-type	clean
X-purgate-Ad	Categorized by eleven eXpurgate (R) http://www.eleven.de
X-purgate	This mail is considered clean (visit http://www.eleven.de for further information)
X-purgate	clean
X-purgate-size	1504
X-purgate-ID	154282::1452712105-000018ED-FB798E08/0/0
X-BeenThere	python-list@python.org
X-Mailman-Version	2.1.20+
Precedence	list
List-Id	General discussion list for the Python programming language <python-list.python.org>
List-Unsubscribe	<https://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	<https://mail.python.org/mailman/listinfo/python-list>, <mailto:python-list-request@python.org?subject=subscribe>
Xref	csiph.com comp.lang.python:101634

Show key headers only | View raw

On 13.01.2016 12:20, Cem Karan wrote:
> On Jan 12, 2016, at 11:18 AM, "Sven R. Kunze" <srkunze@mail.de> wrote:
>
>> Thanks for replying here. I've come across these types of wrappers/re-implementations of heapq as well when researching this issue. :)
>>
>> Unfortunately, they don't solve the underlying issue at hand which is: "remove item from heap with unknown index" and be efficient at it (by not using _heapq C implementation).
>>
>>
>> So, I thought I did another wrapper. ;) It at least uses _heapq (if available otherwise heapq) and lets you remove items without violating the invariant in O(log n). I am going to make that open-source on pypi and see what people think of it.
> Is that so?  I'll be honest, I never tested its asymptotic performance, I just assumed that he had a dict coupled with a heap somehow, but I never looked into the code.

My concern about that specific package is a missing C-implementation. I 
feel that somewhat defeats the whole purpose of using a heap: performance.

Asymptotic performance is still O(log n).

> That said, IMHO using a dict interface is the way to go for priority queues; it really simplified my code using it!  This is my not-so-subtle way of asking you to adopt the MutableMapping interface for your wrapper ;)

Could you elaborate on this? What simplified you code so much?

I have been using heaps for priority queues as well but haven't missed 
the dict interface so far. Maybe, my use-case is different.

Best,
Sven

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

Thread

Re: How to remove item from heap efficiently? "Sven R. Kunze" <srkunze@mail.de> - 2016-01-13 20:08 +0100

csiph-web