[Date Prev][Date Next][Thread Prev][Thread Next]
- Subject: Re: efficient timers
- From: Nagaev Boris <bnagaev@...>
- Date: Mon, 13 Apr 2015 08:38:36 +0000
On Mon, Apr 13, 2015 at 8:17 AM, Oliver Kroth <firstname.lastname@example.org> wrote:
> Hi Thijs,
> not sure if someone else referred to a solution like mine:
> I used in one of my projects a so called binary heap as "queue". New events
> are inserted at the end and bubbled up. Deleted timers leave a hole that is
> filled by inserting the last element and resort the heap. Checking whether
> the first (earliest) event is due can be done in O(1) by looking on the
> heap's root. Inserting and deleting events can be done in O(log n). The
> funny thing is that the heap does not use pointers but is stored in a
> contiguous array using the event's index to calculate the parent's and
> children's indexes.
> May not be the most efficient solution but had the smallest overhead on
> checking the due events, and has reasonable effort on queue management.
> The Lua implementations is about 100 LOC.
> If someone is interested, I may post it.
> Oliver Kroth
I am interested. Could you post it, please?