Re: Decent datastructure for queue operations

meng wrote:
> Hi guys,
>
> I've been developing a tool which has to use lots of queues, well a
> FIFO data structure. So far, I used lists but they are obviously not
> efficient as enqueue operation can take linear time (this is because
> existing entries are not enqueued again, and we need to sort of search
> the queue).

So this is obviously not an ordinary queue. It's some kind of
idempotent queue where you can try to queue an item more than once, in
which case the additional queue operations do nothing.

You know, maybe that can be accomplished with a flag in the queue node
indicating that it's queued.

In C, I might use a doubly-linked list: next and previous pointers in
each node. A node that is not inserted into a queue would have these
pointers set to null.

If you wanted to ensure that no data item is queued more than once into
the same queue, you could simply augment the list with a hash. There is
no reason why you can't use two data structures in parallel.

Regular Lisp lists can be used for FIFOs where the enqueue and dequeue
operations are constant time. Just keep track of the tail and add to
the queue by destructively manipulating the CDR at the tail.

> Binary search has come into mind, but vector is still not a
> good candidate due to difficulty of insertion.

The vector would have to be sorted in order to support a binary search.
You didn't mention that it's a priority queue. Finding the place to
insert will take log n, but the linear time of opening a gap will
dominate that.

> Binary search tree might
> be an option, so...

Balanced binary search trees such as red-black trees are useful for
priority queues. If you don't need to retrieve items in priority order,
it's a waste.

.

Relevant Pages

  • [RFC][PATCH 3/9] cgroups: block: cfq: I/O bandwidth controlling subsystem for CGroups based on CFQ
    ... Extends the original CFQ data sructures and adds the major cfqio_subsys ... * Each block device managed by CFQ I/O scheduler is represented ... * One more basic CFQ scheduler data structure is cfq_queue, ... * which is a queue of requests. ...
    (Linux-Kernel)
  • Re: after ids
    ... Hmm, with only a very slightly smarter data structure, you can have ... Have a hash table that maps afterID to the after event's data ... The after events' data structures are kept in a priority queue ...
    (comp.lang.tcl)
  • Re: Decent datastructure for queue operations
    ... Binary search tree might ... Use a queue data structure built on top of lists: ... the first and to the last last cons cell. ...
    (comp.lang.lisp)
  • Re: Decent datastructure for queue operations
    ... > the queue). ... Binary search tree might ... > - or if a binary search tree is really a great idea, ... For a priority queue, you need a more sophisticated data structure, ...
    (comp.lang.lisp)
  • Re: [PATCH] New operation for kref to help avoid locks
    ... >> likely be with the main data structure ... In your queue example, it would usually be better to have ... > a refcount for being on queue, ... then you would need a lock. ...
    (Linux-Kernel)
Loading