[vdr] Problems with 20 Timers
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?
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).
More information about the vdr