Re: Choice of data structure for large event queues?

From: Thad Smith (thadsmith_at_acm.org)
Date: 12/24/04 

Date: Thu, 23 Dec 2004 22:56:19 -0600

Chris McDonald wrote:
>
> 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.

I haven't used calendar queues, but did some reading from the net.
How many buckets do you use for the events and what are the average
number of elements per bucket? The cost of deleting an element should
be basically the cost of finding the element to be deleted. If you
have a pointer to the item to be deleted, then the cost is very
small. If you have to search for it, then, to my understanding,
finding the element is proportional to the number of items in the
bucket, which is the same cost as choosing the minimum if the bucket
is unsorted or doing an insertion if the bucket is sorted. Either
way, the cost should be similar to insertion or minimum item removal.

Thad

Relevant Pages

  • Re: Intelligent life
    ...  You are talking about translation machines. ... Liquidity is a matter of confidence. ... bucket has parts being thrown into it randomly by other robots working ... I did say a REALISTIC simulation. ...
    (sci.space.policy)
  • Re: Intelligent life
    ... gaseous supergiants. ... but not everyone agrees on a "hard" singularity. ... Take a bucket of parts and tell ... I did say a REALISTIC simulation. ...
    (sci.space.policy)
  • Re: Choice of data structure for large event queues?
    ... >be basically the cost of finding the element to be deleted. ... >bucket, which is the same cost as choosing the minimum if the bucket ... with the calendar queue. ... Similarly deleting a found event is easy - ...
    (comp.programming)
  • Re: Choice of data structure for large event queues?
    ... Thad Smith wrote: ... > be basically the cost of finding the element to be deleted. ... > bucket, which is the same cost as choosing the minimum if the bucket ... costlyer. ...
    (comp.programming)
  • Re: Its not Just Joel Salatin anymore
    ... impregnated the cow last week. ... however the vet was up to his armpit and cost me $80 ... does not see me put feed in the bucket. ... neighbor bails hay for me. ...
    (rec.gardens.edible)