Constant time insertion into a sorted list?

[hackerbob]

I'm trying to create a constant time event timer. Basically, a routine
can set a callback to be called n ms from the current time, and the
main event loop will wait until the delta between the current time and
the earliest event timer has elapsed. When the list is sorted,
checking for expiration is O(n) time where n is the number of timers
that have expired, or O(1) in the case where no timers have expired
(which is important in an I/O event/timer loop). We do this by walking
up the list from the tail until we reach the end, or the first timer
that will expire in the future.

Adding or updating a timer can be constant time if every time interval
from the current time is constant. If every timer will fire 5 seconds
from when the timer is set, it's a simple matter of pushing all new
timers to the tail of the list, and it remains sorted.

Has there been an algorithm invented yet that can insert a non-
constant integer (time until this timer expires) into a list of
integers (other timers) such that the list remains sorted in constant
time?

The only obvious choice that comes to mind is a divide-and-conquer
algorithm that continually divides the timer space in half until two
timers are found that are between the timer being inserted. But that
would take O(log n) where n is the number of timers in the list.
Getting progressively worse as more timers are added.

Timer wheels from the Linux kernel scheduler are fairly attractive
(radix sorting approach), but insertion isn't always constant if the
date is too far into the future.

Anyone have any ideas? If I think of something awesome, I will report
back. :)

Bob

[Dann Corbit]

<ha*******@gmail.comwrote in message
news:70**********************************@59g2000h sb.googlegroups.com...

I'm trying to create a constant time event timer. Basically, a routine
can set a callback to be called n ms from the current time, and the
main event loop will wait until the delta between the current time and
the earliest event timer has elapsed. When the list is sorted,
checking for expiration is O(n) time where n is the number of timers
that have expired, or O(1) in the case where no timers have expired
(which is important in an I/O event/timer loop). We do this by walking
up the list from the tail until we reach the end, or the first timer
that will expire in the future.

Adding or updating a timer can be constant time if every time interval
from the current time is constant. If every timer will fire 5 seconds
from when the timer is set, it's a simple matter of pushing all new
timers to the tail of the list, and it remains sorted.

Has there been an algorithm invented yet that can insert a non-
constant integer (time until this timer expires) into a list of
integers (other timers) such that the list remains sorted in constant
time?

The only obvious choice that comes to mind is a divide-and-conquer
algorithm that continually divides the timer space in half until two
timers are found that are between the timer being inserted. But that
would take O(log n) where n is the number of timers in the list.
Getting progressively worse as more timers are added.

Timer wheels from the Linux kernel scheduler are fairly attractive
(radix sorting approach), but insertion isn't always constant if the
date is too far into the future.

Anyone have any ideas? If I think of something awesome, I will report
back. :)

Calendar queues and implicit binary heaps are approximately O(1) for the
enqueue operation.
http://www.leekillough.com/heaps/pap...7-ronngren.pdf

news:comp.programming is a better choice than news:comp.lang.c since you
don't appear to have a C question that I can discern.
** Posted from http://www.teranews.com **