Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #101631

Re: How to remove item from heap efficiently?

Show key headers only | View raw

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

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

Thread

Re: How to remove item from heap efficiently? Robin Becker <robin@reportlab.com> - 2016-01-13 16:40 +0000

csiph-web