On 13.01.2016 12:20, Cem Karan wrote:
On Jan 12, 2016, at 11:18 AM, "Sven R. Kunze" <srku...@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
--
https://mail.python.org/mailman/listinfo/python-list
