What is a Franta-Maly event list? Is there a C++ implementation available?

[Andrew]

I am implementing a process that performs a very similar job to the
cron daemon. After a bit of research I find that the original cron
implementation had a performance problem. Waking up every minute and
checking the whole scheduled task list proved inefficient, compared
with sleeping until it is time to start the first job. I read
somewhere that using the ordered list was done by constructing a
Franta-Maly event list. Unfortunately I have been unable to find out
more about this structure. The ACM paper that describes it was
published back in 1977 but you still have to pay to get it. I was
hoping that documentation would be more generally available by now.

I was wondering, has anybody here heard of a Franta-Maly event list? I
wonder if it similar to the priority queue in the STL.

Regards,

Andrew Marlow

[Mathias Gaunard]

Post by Andrew
I read
somewhere that using the ordered list was done by constructing a
Franta-Maly event list. Unfortunately I have been unable to find out
more about this structure. The ACM paper that describes it was
published back in 1977 but you still have to pay to get it. I was
hoping that documentation would be more generally available by now.

You can probably find a free alternative version using google scholar.

[m***@gmail.com]

Post by Andrew
I am implementing a process that performs a very similar job to the
cron daemon. After a bit of research I find that the original cron
implementation had a performance problem. Waking up every minute and
checking the whole scheduled task list proved inefficient, compared
with sleeping until it is time to start the first job. I read
somewhere that using the ordered list was done by constructing a
Franta-Maly event list. Unfortunately I have been unable to find out
more about this structure. The ACM paper that describes it was
published back in 1977 but you still have to pay to get it. I was
hoping that documentation would be more generally available by now.
I was wondering, has anybody here heard of a Franta-Maly event list? I
wonder if it similar to the priority queue in the STL.

Hi Andrew,

I don't know this kind of data structure, but from the article's
abstract I read that it's complexity is O(\sqrt{n}) which is worst
than that of a priority queue, O(\log{n}).

Usually std::priority_queue (used with its default settings, that is
with an std::vector as its underlying container) offers good
performance.
If you need some efficient data structure for discrete-event
simulation you may want to take a look at calendar queues, e.g.:

- Main reference: http://doi.acm.org/10.1145/63039.63045
- Short description + link to implementation:
http://www.itl.nist.gov/div897/sqg/dads/HTML/calendarQueue.html
- A recently proposed variant (suitable for skewed event
distributions): http://www.informs-sim.org/wsc00papers/068.PDF

Best,

-- Marco