Path: csiph.com!news.swapon.de!fu-berlin.de!uni-berlin.de!not-for-mail
From: Cem Karan <cfkaran2@gmail.com>
Newsgroups: comp.lang.python
Subject: Re: Heap Implementation
Date: Thu, 11 Feb 2016 06:06:00 -0500
Lines: 67
Message-ID: <mailman.45.1455188766.22075.python-list@python.org>
References: <56AD3D83.2050308@mail.de> <7C522D08-9D73-48D2-A71D-F1D1D34C02A5@gmail.com> <56BB8005.8090708@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: <56BB8005.8090708@mail.de>
Precedence: list
Xref: csiph.com comp.lang.python:102802


On Feb 10, 2016, at 1:23 PM, "Sven R. Kunze" <srkunze@mail.de> wrote:

> Hi Cem,
>=20
> On 08.02.2016 02:37, Cem Karan wrote:
>> My apologies for not writing sooner, but work has been quite busy =
lately (and likely will be for some time to come).
>=20
> no problem here. :)
>=20
>> I read your approach, and it looks pretty good, but there may be one =
issue with it; how do you handle the same item being pushed into the =
heap more than once?  In my simple simulator, I'll push the same object =
into my event queue multiple times in a row.  The priority is the moment =
in the future when the object will be called.  As a result, items don't =
have unique priorities.  I know that there are methods of handling this =
from the client-side (tuples with unique counters come to mind), but if =
your library can handle it directly, then that could be useful to others =
as well.
>=20
> I've pondered about that in the early design phase. I considered it a =
slowdown for my use-case without benefit.
>=20
> Why? Because I always push a fresh object ALTHOUGH it might be equal =
comparing attributes (priority, deadline, etc.).
>=20
>=20
> That's the reason why I need to ask again: why pushing the same item =
on a heap?
>=20
>=20
> Are we talking about function objects? If so, then your concern is =
valid. Would you accept a solution that would involve wrapping the =
function in another object carrying the priority? Would you prefer a =
wrapper that's defined by xheap itself so you can just use it?

Yes.  I use priority queues for event loops.  The items I push in are =
callables (sometimes callbacks, sometimes objects with __call__()) and =
the priority is the simulation date that they should be called.  I push =
the same item multiple times in a row because it will modify itself by =
the call (e.g., the location of an actor is calculated by its velocity =
and the date). There are certain calls that I tend to push in all at =
once because the math for calculating when the event should occur is =
somewhat expensive to calculate, and always returns multiple dates at =
once. =20

That is also why deleting or changing events can be useful; I know that =
at least some of those events will be canceled in the future, which =
makes deleting useful.  Note that it is also possible to cancel an event =
by marking it as cancelled, and then simply not executing it when you =
pop it off the queue, but I've found that there are a few cases in my =
simulations where the number of dead events that are in the queue =
exceeds the number of live events, which does have an impact on memory =
and operational speed (maintaining the heap invariant).  There isn't =
much difference though, but I need FAST code to deal with size of my =
simulations (thousands to tens of thousands of actors, over hundreds of =
millions of simulations, which is why I finally had to give up on python =
and switch to pure C).

Having a wrapper defined by xheap would be ideal; I suspect that I won't =
be the only one that needs to deal with this, so having it centrally =
located would be best.  It may also make it possible for you to optimize =
xheap's behavior in some way.

Thanks,
Cem Karan=