Path: csiph.com!fu-berlin.de!uni-berlin.de!not-for-mail
From: Robin Becker <robin@reportlab.com>
Newsgroups: comp.lang.python
Subject: Re: How to remove item from heap efficiently?
Date: Wed, 13 Jan 2016 16:40:29 +0000
Lines: 21
Message-ID: <mailman.112.1452703239.13488.python-list@python.org>
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> <CACs7g=B-kNiqB5p1Zs3dyp1vW7P=K4bwG_HzGkX_83Z7Y6uHMg@mail.gmail.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 7bit
X-Trace: news.uni-berlin.de MyWpcdd1NPIXJafNwOyyzQ+dpNsFe7vefZUh3WVDbK7g==
Return-Path: <python-python-list@m.gmane.org>
X-Original-To: python-list@python.org
Delivered-To: python-list@mail.python.org
X-Spam-Status: OK 0.000
X-Spam-Evidence: '*H*': 1.00; '*S*': 0.00; 'so?': 0.07; 'subject:How': 0.09; 'assumed': 0.09; 'dict': 0.09; 'mutable': 0.09; 'received:80.91': 0.09; 'received:80.91.229': 0.09; 'received:gmane.org': 0.09; 'received:list': 0.09; 'python': 0.10; 'assume': 0.11; 'jan': 0.11; 'wed,': 0.15; '2016': 0.16; 'accesses': 0.16; 'amortized': 0.16; 'heap': 0.16; 'heap,': 0.16; 'heapq': 0.16; 'received:80.91.229.3': 0.16; 'received:io': 0.16; 'received:plane.gmane.org': 0.16; 'received:psf.io': 0.16; 'somehow,': 0.16; 'subject:item': 0.16; 'subject:remove': 0.16; 'wrote:': 0.16; 'looked': 0.16; 'element': 0.18; 'fixed.': 0.18; '(the': 0.22; 'amounts': 0.22; 'code,': 0.23; 'code.': 0.23; 'references': 0.23; 'header:In-Reply-To:1': 0.24; 'header:User- Agent:1': 0.26; 'header:X-Complaints-To:1': 0.26; 'url:moin': 0.27; '13,': 0.29; 'lot.': 0.29; 'understand,': 0.29; 'url:wiki': 0.30; 'code': 0.30; 'guess': 0.31; 'says': 0.32; 'point': 0.33; 'class': 0.33; 'url:python': 0.33; 'operations.': 0.33; "i'll": 0.33; 'list': 0.34; 'quite': 0.35; 'but': 0.36; 'list,': 0.36; 'there': 0.36; 'url:org': 0.36; 'to:addr:python-list': 0.36; 'subject:?': 0.36; 'pm,': 0.36; 'subject:: ': 0.37; 'received:org': 0.37; 'seem': 0.37; 'delete': 0.38; 'subject:from': 0.39; 'to:addr:python.org': 0.40; 'some': 0.40; 'times': 0.63; 'received:109': 0.75; 'becker': 0.84; 'coupled': 0.84; 'technically': 0.91; 'average': 0.93
X-Injected-Via-Gmane: http://gmane.org/
X-Gmane-NNTP-Posting-Host: 109.174.168.73
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:38.0) Gecko/20100101 Thunderbird/38.5.1
In-Reply-To: <CACs7g=B-kNiqB5p1Zs3dyp1vW7P=K4bwG_HzGkX_83Z7Y6uHMg@mail.gmail.com>
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:101631

On 13/01/2016 15:34, srinivas devaki wrote:
> On Wed, Jan 13, 2016 at 4:50 PM, Cem Karan <cfkaran2@gmail.com> wrote:
>>
>> 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.
>>
>
> I have just tested the code, the aymptotic performance is O(log(n))
> for all operations. Infact the code is very simple to understand,
> technically the heapdict class is composed of a dict and heap, each element of
> heap is a mutable list and dict stores references to that mutable list,
> so that a specific element can be deleted in O(log(n))
>
is this true? I looked at https://wiki.python.org/moin/TimeComplexity and it 
says that dict.get which I assume is used for accessing the heapq delete point 
can be large (the average time is O(1), but amortized over a lot of accesses can 
be O(n)). Apparently the history of sets/gets can affect individual times quite 
a lot. I seem to remember there was some kind of hashing attack against python 
dicts that would use up large amounts of time, but I guess that's now fixed.
-- 
Robin Becker