Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl-Sensitive Sunglasses

Data Structure needed for Event Queue

by vaevictus (Pilgrim)
on May 27, 2002 at 16:34 UTC ( #169614=perlquestion: print w/replies, xml ) Need Help??

vaevictus has asked for the wisdom of the Perl Monks concerning the following question:

I'm working on a game, and I need to give it a time based event queue. I'm concerned about efficiency, to an extent.

Here are my problems:

  • events might be very far apart, but could also be on the *exact* same time.
  • I'm wanting to be able to cancel out events.
  • I'd two simple interfaces, push($time,$eventref), and $eventref=pop(); which returns one of the events from the lowest $time.
  • It seems to me that a comparison tree, or a ternary tree would be fine, but haven't found any that would be appropriate to use over just coding this by hand.

Array of Arrays seems inefficient when the nodes are very far apart, requiring lots of iteration, and i'm not so sure how it would scale when i've inserted and removed millions of events.

Hashes of Arrays seems better about most things, but requires a expensive sort every pop(), or possibly a sort upon each new timestamp needed, if you store the "lowest" somewhere.

I'm sure TMTOWTDI.
Any modules out there that might help out?
Or, any suggestions on how to do this efficiently?

Replies are listed 'Best First'.
•Re: Data Structure needed for Event Queue
by merlyn (Sage) on May 27, 2002 at 16:38 UTC
    You could always just shove it into a database with an index. {grin}

    I'm not a CS expert, but I think a B-tree might be the right structure (see Pure Perl B-Tree managers are available, such as Tree and Btrees. I think even a Berkeley DB can be stored "in core" with the BerkeleyDB module, and there's a B-Tree version of that.

    -- Randal L. Schwartz, Perl hacker

    update: yes, with DB_File, you can set up an in-memory DB (use undef for the filename), and with the right comparison callback, you get basic operations like
    ## add a new $nextevent at $time: push @{$db{$time}}, $nextevent; ## get the lowest event list keys %db; # reset pointer my ($time, $events) = each %db; # lowest events
Re: Data Structure needed for Event Queue
by Zaxo (Archbishop) on May 27, 2002 at 21:01 UTC
      Like a number of others in the monastery, I would suggest you not use Heap. This may be one of those rare cases where it's faster and more reliable to write and debug your own version than go to CPAN. Alternatively, the authors of "Elements of Programming with Perl" have been kind enough to put a kinder, gentler implementation on the web. I haven't tested it, but it's at least simple enough that it's possible to read and understand the code, and relatively painless to use it.


        Just curious, but without my references im not really sure but what kind of heap is that? Fibonnacci?

        Yves / DeMerphq
        Writing a good benchmark isnt as easy as it might look.

Re: Data Structure needed for Event Queue
by jarich (Curate) on May 28, 2002 at 05:10 UTC
    How about an array of hashes? Each search could then be done using a binary search (if you need to search), each pop is a pop, each push is a push (or if you're perverse a shift and an unshift). Your hash would of course contain your timestamp and eventref.

    Looking at your requirements:

    • Events may be far apart. No problem.
    • Events may be at the same time. No problem.
    • $queue->qpush($time, $eventref) No problem:
      sub qpush { my ($self, $time, $eventref) = @_; push @{$self}, {time=>$time, event=>$eventref}; }
      (assuming you treat the queue as an object and it's underlying structure is an arrayref).
    • $eventref = $queue->qpop(); No problem:
      sub qpop { my ($self) = @_; my $ref = pop @{$self}; return $ref->{event}; }
      Update:The astute will have spotted this, but that "pop" up there really ought to be a "shift". I won't change it, but if you use this code, hopefully you will.

    Of course you might want an insert function as well, that's where binary searching would come in:

    # to call it: $queue->qinsert($time, $eventref); # implementation sub qinsert { my ($self, $time, $eventref) = @_; unless (@{$self} > 0) { return $self->qpush($time, $eventref); } my $bot = 0; my $top = @$self - 1; my $mid = int (@{$self} / 2); while(1) { # put it before this bottom place if($time < $self->[$bot]{time}) { my @new = (@$self[0..($bot-1)], {time=>$time, event=>$eventref}, @$self[$bot..(@$self -1)] ); @{$self} = @new; return; } # put it after the top place elsif($time > $self->[$top]{time}) { my @new = (@$self[0..$top], {time=>$time, event=>$eventref}, @$self[($top+1)..(@$self - 1)] ); @{$self} = @new; return; } # put it in the middle here elsif($top - $bot == 1) { my @new = (@$self[0..$bot], {time=>$time, event=>$eventref}, @$self[$top..(@$self-1)] ); @{$self} = @new; return; } # else it's somewhere between my $mid = int(($top - $bot)/2 + $bot); if($time < $self->[$mid]{time}) { $top = $mid; } else { $bot = $mid; } } }
    Of course the implementation can always be different too. :) I've only ever writen a binary search/insert in C and I can tell that it shows.

    Hope this helps.


(MeowChow) Re: Data Structure needed for Event Queue
by MeowChow (Vicar) on May 28, 2002 at 06:54 UTC
    Have you considered using Event instead of rolling your own?
                   s aamecha.s a..a\u$&owag.print
Re: Data Structure needed for Event Queue
by Anonymous Monk on May 27, 2002 at 16:40 UTC
    A Heap as a priority queue.

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://169614]
Approved by cjf
Front-paged by MeowChow
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others surveying the Monastery: (5)
As of 2021-01-24 01:05 GMT
Find Nodes?
    Voting Booth?