Skiplists

[Andreas Ericsson]

Einar Indridason wrote:
>>>>>>> Ethan Galstad wrote:
>>>>>>>>> For the event queue, I was thinking that a skip
>>>>>>>>> list structure might be best for efficiency
>>>>>>>>> (http://en.wikipedia.org/wiki/Skip_list).  The
>>>>>>>>> event queue is used in primarily two
>>>>>>>>> situations:
>>>>>>>>> 1. Popping events from the head of the list to
>>>>>>>>>    be executed
>>>>>>>>> 2. Inserting events into the list (mid- or
>>>>>>>>>    endpoint).
> 
> 
> 
> Sorry for butting in so late in this discussion.  But have you considered a
> "Heap" (or a priority queue)?
> (Or maybe I'm misunderstanding something here?)
> 
> http://en.wikipedia.org/wiki/Heap_%28data_structure%29
> http://en.wikipedia.org/wiki/Priority_queue
> 
> This will allow you, with ease, to get the "lowest" priority.  (It is the
> first item on the heap).

It's not so much about priority as it is about timeboxing. The current code
gets the first item immediately too. It's finding where to insert things
that's the trouble, since it's a time-ordered linked list.


> Time complexity of retrieval is of order: O(n * log(n))
> Adding an item, with assorted priority, is also of order: O(n * log(n))
> 

Which is worse than the skiplists, and possibly (but not probably) better
than the time-hash algorithm.

The time-hash algorithm ("mine", if you so wish) is a fixed value of three
statements to insert a new value. Finding a specific value is not quite so
easy, but I'd imagine that could be solved to be a 1-op value if one just
adds an event-struct pointer to the host and service objects. I'm not so
sure how to handle downtime, or other scheduled items where it's not obvious
to store the event-data pointer.

Finding the place to start at in the scheduling queue is 1 statement more
expensive than earlier, although that could be taken care of by simply
maintaining the "last emptied timeslot" as a static variable in function
scope.

But enough of that. I haven't had a chance to touch a keyboard all day,
and my finger's been itching for quite some time now, so it's time I
get on with it. I'll abstract the event-code out first, so that other
algorithms can be tested fairly easily, and then get to work with
implementing the time-hash thing, and possibly the skiplist stuff as
well, for comparison if nothing else.

-- 
Andreas Ericsson                   andreas.ericsson at op5.se
OP5 AB                             www.op5.se
Tel: +46 8-230225                  Fax: +46 8-230231

-------------------------------------------------------------------------
This SF.net email is sponsored by: Splunk Inc.
Still grepping through log files to find problems?  Stop.
Now Search log events and configuration files using AJAX and a browser.
Download your FREE copy of Splunk now >> http://get.splunk.com/