Path: csiph.com!fu-berlin.de!uni-berlin.de!not-for-mail From: Cem Karan Newsgroups: comp.lang.python Subject: Re: How to remove item from heap efficiently? Date: Wed, 13 Jan 2016 06:20:17 -0500 Lines: 39 Message-ID: References: <568EEC40.7070807@mail.de> <568FE797.6090808@mail.de> <5692A795.3070904@mail.de> <5695276A.2020101@mail.de> Mime-Version: 1.0 (Mac OS X Mail 6.6 \(1510\)) Content-Type: text/plain; charset=windows-1252 Content-Transfer-Encoding: quoted-printable X-Trace: news.uni-berlin.de aB536MLc7UO6AdWs45S5FwAE+6/pd2ZV9f+7cxoyKLXA== Return-Path: 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; '_heapq': 0.16; 'heap': 0.16; 'heapq': 0.16; 'jumping': 0.16; 'received:192.168.1.4': 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:2**1': 0.22; '(by': 0.22; 'cc:no real name:2**0': 0.22; 'am,': 0.23; 'code.': 0.23; "haven't": 0.24; 'thanks,': 0.24; 'cc:addr:gmail.com': 0.24; 'header:In-Reply-To:1': 0.24; "i've": 0.25; 'least': 0.27; 'said,': 0.27; 'interface': 0.29; '"remove': 0.29; 'that.': 0.30; 'code': 0.30; 'another': 0.32; 'though,': 0.32; 'lets': 0.33; "i'll": 0.33; 'message-id:@gmail.com': 0.34; 'received:google.com': 0.35; 'so,': 0.35; 'unknown': 0.35; 'quite': 0.35; 'something': 0.35; 'asking': 0.35; 'item': 0.35; 'but': 0.36; 'received:209.85': 0.36; 'subject:?': 0.36; 'subject:: ': 0.37; 'really': 0.37; 'thanks': 0.37; '12,': 0.37; 'thought': 0.37; 'received:209': 0.38; 'received:209.85.220': 0.38; 'subject:from': 0.39; 'received:192': 0.39; 'well.': 0.40; 'your': 0.60; 'skip:u 10': 0.61; 'header:Message-Id:1': 0.61; 'replying': 0.61; 'here.': 0.62; 'charset:windows-1252': 0.62; 'skip:n 10': 0.62; 'it!': 0.64; 'past,': 0.66; 'hand': 0.82; 'coupled': 0.84; 'late,': 0.84; 'researching': 0.84; 'adopt': 0.91 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=content-type:mime-version:subject:from:in-reply-to:date:cc :content-transfer-encoding:message-id:references:to; bh=5wUoeSw46spVwmRcIKmvyIyzkhi71RxFFSUgyP+Xumk=; b=pgNtlaJIqbg1xoX4a98MViGwpA0+d0HbiqqguiWcTbPIsw/LKGJLA2aWd7yorckhD1 tH/b5IYC43m904H5S1iV6P/WdtZ1nat8YThjIUJPUa21vwaLS6XFRKniVD6cSVw3zO20 CybSxbQ8UQtK8SUPWIXW2WRFsGivDFhcPZUs/YaQROT2hE1Ga9+kjKOhH7vdtZawiBMB Rm7uh+zaTGZ43qtlpmPKk8NzqpOw21VCMW7vvkvsuIrR5oCapiO8DQwHOikN8PFKKmsd OaTnyBWXdbtYyK30kkZBQOcsl52cko8AVpqUQw2bVRoq0PUV7ZIcKgLjVekw4DrgmdO6 uk8w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:content-type:mime-version:subject:from :in-reply-to:date:cc:content-transfer-encoding:message-id:references :to; bh=5wUoeSw46spVwmRcIKmvyIyzkhi71RxFFSUgyP+Xumk=; b=lh7Uy0pxHR2r/MrhGCJi3XudKBw5ASh0BOwE1J/l6W4obXKa0jzNOWnEJwOffaedsE xmNeUSkI6PjnJi31p2DezNMnZpJtcezsUMIrjNuHC7z67OBrKLJnV2S0DgZJTxhL4U1e CKBf/rJDYGnPR51DTcHBtbjgIdYoGIXutkzSkdlomUAxCBylwAY/HHlGxNu0u6FezMtT m6p/wr9TIsdnVCInitwQMly1tc9igQ29/b0xRrNAzdbYirOujR13Af59UIOd7EhzpMmX ijInxgt/6vqcO36U97I+F31EX/xoKpJXc1b6/Zcex7EDQOT2GzJpUJA5epCrAG70KKXy eAQw== X-Gm-Message-State: ALoCoQnUPJeBZCsUVPR8QAFw89dmbutzFvF9Xn4sVI7bkpPvApTNLWF1T8BIT3l3F+FukbIYyL2HHdqzmh9QkXUcyO7iiu1Q6g== X-Received: by 10.55.82.193 with SMTP id g184mr180077510qkb.65.1452684016619; Wed, 13 Jan 2016 03:20:16 -0800 (PST) In-Reply-To: <5695276A.2020101@mail.de> X-Mailer: Apple Mail (2.1510) X-BeenThere: python-list@python.org X-Mailman-Version: 2.1.20+ Precedence: list List-Id: General discussion list for the Python programming language List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Xref: csiph.com comp.lang.python:101602 On Jan 12, 2016, at 11:18 AM, "Sven R. Kunze" wrote: > On 12.01.2016 03:48, Cem Karan wrote: >>=20 >> Jumping in late, but... >>=20 >> If you want something that 'just works', you can use HeapDict: >>=20 >> http://stutzbachenterprises.com/ >>=20 >> I've used it in the past, and it works quite well. I haven't tested = its asymptotic performance though, so you might want to check into that. >=20 > Thanks for replying here. I've come across these types of = wrappers/re-implementations of heapq as well when researching this = issue. :) >=20 > 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). >=20 >=20 > 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. 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 = ;) Thanks, Cem Karan=