Choice of data structure for large event queues?

From: Chris McDonald (chris_at_csse.uwa.edu.au)
Date: 12/23/04 

Date: Thu, 23 Dec 2004 11:02:27 -0600

Hello, I have been implementing and measuring calendar-queues to manage
time-ordered event queues in a simulation.

The basic functions of enqueuing and dequeuing work very well (very fast)
for simulations involving thousands, even hundreds of thousands,
of pending events.

However, my simulation also needs to occassionally, maybe 2% of the time,
remove a "random" event from the queue - keeping the the queue
balanced/ordered correctly for the more frequent enqueuing and dequeuing.
Of course, with calendar-queues, this degenerates to linear behaviour -
which is woeful.

Does anyone have suggestions for other data structures that I should
examine? Thanks in advance,

______________________________________________________________________________
Dr Chris McDonald E: chris@csse.uwa.edu.au
Computer Science & Software Engineering W: http://www.csse.uwa.edu.au/~chris
The University of Western Australia, M002 T: +618 6488 2533
Crawley, Western Australia, 6009 F: +618 6488 1089

Relevant Pages

  • Re: Red Hat thread sync question
    ... My first job was at a University, in a new IBM shop. ... Instead, I put in a batch-system, and forced all of the simulation runs to ... completion rate of about 2 jobs a minute no matter how large the queue ... arrive, the manager doesn't add water to an "instant food preparer" box, ...
    (comp.os.linux.networking)
  • Re: Synthesis friendly code?
    ... the first of which triggers the @event control. ... end of the Active queue, which will be after the second NB Assign, ... evaluation event on the queue for a given process, ... simulation network, and not produce any other change of state (running ...
    (comp.lang.verilog)
  • Re: Xilinx XST Error
    ... Search for synthesizable VHDL references. ... valuedoes not match array range, simulation mismatch. ... entity queue is ... elsif falling_edgethen ...
    (comp.lang.vhdl)
  • Re: Choice of data structure for large event queues?
    ... >Since this is a simulation perhaps you can solve this problem with ANOTHER ... Instead of actually deleting a random event, ... front of the calendar queue, just ignore it and find the next real event. ...
    (comp.programming)
  • Re: Choice of data structure for large event queues?
    ... Since this is a simulation perhaps you can solve this problem with ANOTHER ... Instead of actually deleting a random event, ... > The basic functions of enqueuing and dequeuing work very well ...
    (comp.programming)