lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]

On Mon, Apr 13, 2015 at 6:45 AM, Thijs Schreijer
<> wrote:
> Thx for the info, but maybe my question should have been clearer. Timer functionality basically consists of 3 parts;
> 1 - a ticking clock
> 2 - a task execution method
> 3 - timer management (scheduling and cancelling of timers)
> The methods listed above concern mostly 1, and a bit of 2. Whilst I'm looking for an efficient way to do 3.
> Consider a server with 1000 connections, each having a timeout timer. Most timers never execute, they are just fallbacks. Having a sorted linked list in this situation, would require traversal of that linked list for each timer added (called an O(n) operation if I'm not mistaken), which is costly performance wise. I would like an algorithm that has O(1) for both scheduling and cancellation of timers (once again if I'm not mistaken, I'm not that familiar with this O notation stuff).
> A timing-wheel is such an algorithm. See (link by Nathan)
> Thijs

Can you use red-black tree to add and remove timers in O(ln N)?

Best regards,
Boris Nagaev