[vdr] Problems with 20 Timers

Carsten Koch Carsten.Koch at icem.com
Fri Feb 25 20:05:07 CET 2005


Olaf Titz wrote:
>>I wonder if it would be worth rewriting cSchedule to store events in a
>>binary tree based on time. A double-linked list could be included in the
>>nodes pointing to allow for scanning through the schedule in the
>>conventional way (for(cEvent *p = events.First()...)
> 
> 
> The right data structure for this (or rather, the canonical data
> structure for any sort of timer queue) is a binary heap. Guaranteed
> O(log n) time for insert and delete(first) operation and O(1) for
> lookup(first), zero memory overhead and much easier to implement than
> all other sorts of balanced tree.
> 
> 
>>What do people think, would it be worth me writing a patch?
> 
> 
> Definitely.


Come one, guys, you must be kidding!

For a few dozen timers even the simplest data structure has to
perform extremely well, unless there is a bug.

So I suggest keeping the data structure and fixing the bug
(which is propably exactly what Darren's patch does).

Carsten.



More information about the vdr mailing list