On 13/01/2016 15:34, srinivas devaki wrote:
On Wed, Jan 13, 2016 at 4:50 PM, Cem Karan <cfkar...@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
--
https://mail.python.org/mailman/listinfo/python-list
