Skiplists
Einar Indridason
einar.indrida at gmail.com
Tue Oct 16 16:46:02 CEST 2007
>>>>>> 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).
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))
Cheers,
--
EinarI
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://www.monitoring-lists.org/archive/developers/attachments/20071016/0ebb95bb/attachment.html>
-------------- next part --------------
-------------------------------------------------------------------------
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/
-------------- next part --------------
_______________________________________________
Nagios-devel mailing list
Nagios-devel at lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/nagios-devel
More information about the Developers
mailing list