Path: csiph.com!fu-berlin.de!uni-berlin.de!not-for-mail
From: Cem Karan <cfkaran2@gmail.com>
Newsgroups: comp.lang.python
Subject: Re: How to remove item from heap efficiently?
Date: Thu, 14 Jan 2016 07:04:17 -0500
Lines: 87
Message-ID: <mailman.145.1452773062.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> <5696A0A5.8020401@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
In-Reply-To: <5696A0A5.8020401@mail.de>
Precedence: list
Xref: csiph.com comp.lang.python:101685

On Jan 13, 2016, at 2:08 PM, Sven R. Kunze <srkunze@mail.de> wrote:
> On 13.01.2016 12:20, Cem Karan wrote:
>> On Jan 12, 2016, at 11:18 AM, "Sven R. Kunze" <srkunze@mail.de> =
wrote:
>>=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.
>=20
> My concern about that specific package is a missing C-implementation. =
I feel that somewhat defeats the whole purpose of using a heap: =
performance.

I agree with you that performance is less than that of using a C =
extension module, but there are other costs associated with developing a =
C module:

1) As the developer of the module, you must be very careful to ensure =
your code is portable.

2) Distribution becomes somewhat more difficult; you may need to =
distribute both source and compiled binaries for various platforms.  =
This is somewhat more annoying than pure python scripts.

3) Debugging can become significantly more difficult.  My current =
codebase is python+cython+c, and when something crashes, it is usually =
easier to use a bunch of printf() statements to figure out what is going =
on than to use a debugger (others may have different experiences, this =
is just mine).

4) Not everyone is familiar with C, so writing extensions may be more =
difficult.

5) Will the extension module work on non-cpython platforms (iron python, =
jython, etc.)?

Finally, without profiling the complete package it may be difficult to =
tell what impact your C module will have on overall performance.  In my =
code, HeapDict had less than a 2% performance impact on what I was =
doing; even if I had replaced it with a pure C implementation, my code =
would not have run much faster.

So, while I agree in principle to what you're saying, in practice there =
may be other factors to consider before rejecting the pure python =
approach.

> Asymptotic performance is still O(log n).

So, if the intent is to pop events more often than to peek at them, then =
in practice, HeapDict is about the same as some clever heap+dict method =
(which it might be, as I said, I haven't looked at 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 =
;)
>=20
> Could you elaborate on this? What simplified you code so much?
>=20
> 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.


I'm writing an event-based simulator, and as it turns out, it is much =
easier to tentatively add events than it is to figure out precisely =
which events will occur in the future.  That means that on a regular =
basis I need to delete events as I determine that they are garbage.  =
HeapDict did a good job of that for me (for completely unrelated reasons =
I decided to switch to a pure-C codebase, with python hooks to twiddle =
the simulator at a few, very rare, points in time; hence the =
python+cython+c comment above).

Thanks,
Cem Karan=