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

 

[Harold Aptroot]

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?

</snip>

If the list is an array: no, it would already take O(n) steps to do the
insertion (and O(log n) to find the place, no shortcuts)
If the list is a linked list: no, it would already take O(n) steps to reach
the splace of insertion, even if you know the place to be right immediately
upon finding it
But then, there are trees..
Normal trees wouldn't do, but there is this trick.. however you will shortly
see that this trick actually makes time worse in all real life cases.
It's simpel, for each bit in the value, go left or right in the tree (based
on the bit of course). You don't even have to save the value itself, the
information of whether or not a value in the domain (limited by the number
of bits) is in the tree can be retrieved by walking down the path of the
value - if the path reaches the bottom the value is in the tree, otherwise
it isn't. Enumerating all contained values in ascending order is also
trivial.

The downside is that for a given number of bits, this kind of tree allways
takes as many steps to insert a value as a normal binary tree would when it
is completely full - so while the time is constant, it is equal to the worst
case of a normal tree. In practice it may not be that bad since no
restructuring is ever needed and the algorithms are trivial to implement,
but even so, the tree would have to be really gigantic in order to be as
fast as for example a binary rearch tree or skip list


But I'm also curious, might there be a good way to do this?