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). Binary search has come into mind, but vector is still not a
good candidate due to difficulty of insertion. Binary search tree might
be an option, so...
- does anyone here have a better idea?
- or if a binary search tree is really a great idea, are there built-in
LISP functions for it?
Thanks in advance for any idea!
Meng
One way is to write a structure that holds a list L together with a
pointer p to the last cons in the list. To add an item,
(setf (cdr p) (list new-item))
(pop p)
To remove an item,
(pop L)
You'd also have to handle p when L is empty.
mmcconnell17, thanks for your idea. Actually, this is what I've been
using but as I said enqueue is not just append an item like that. The
queue entries are somehow required to be unique.
By the way, LISP has a function `last' which points directly to the
last item of a list without needing to traverse it.
--Meng
Oops.. I was mistaken with the `last' function which of course does not
jump in no time to the end of a list.
Glenn: thanks for the chapter, it's helpful.
To Kaz: the idea of using a hash table along side a list is not a bad
idea, indeed. The only problem I encountered was the data structures
became too big when many queues were in use.
It doesn't have to be a priority queue, but the items should never be
enqueued once they are there.
>>>>> "meng" == meng <·······@gmail.com> writes:
meng>
meng> To Kaz: the idea of using a hash table along side a list is
meng> not a bad idea, indeed. The only problem I encountered was
meng> the data structures became too big when many queues were in
meng> use.
meng> It doesn't have to be a priority queue, but the items should
meng> never be enqueued once they are there.
If your are looking only at EQ uniqueness then I believe a hash-table
will be your best bet. Ultimately there is a trade off between speed
and space requirements - you seem to want both.
If you can compare your items using a less-than type operation then a
priority queue using a binary heap (see Cormen, Leiserson and Rivest,
"Introduction to Algorithms", pp. 140--152, MIT Press) would probably
be more efficient in speed and possibly in space if you control the
heap extension and initial allocation to be appropriate for the
usage. An implementation of this in CL is available from the CMU/AI
depository.
--
John Williams
From: Edi Weitz
Subject: Re: Decent datastructure for queue operations
Date:
Message-ID: <uk6cglo41.fsf@agharta.de>
On 31 Jan 2006 01:42:49 -0800, "meng" <·······@gmail.com> wrote:
> By the way, LISP has a function `last' which points directly to the
> last item of a list without needing to traverse it.
No, that's wrong. LAST has to traverse the list and is thus an O(n)
operation.
We recently had this discussion whether it's possible for an
ANSI-compliant implementation to internally represent lists in a way
that would make your behaviour possible. I forgot the outcome but in
pratice it doesn't matter because all existing Common Lisps do it
alike.
--
Lisp is not dead, it just smells funny.
Real email: (replace (subseq ·········@agharta.de" 5) "edi")
Edi Weitz wrote:
> On 31 Jan 2006 01:42:49 -0800, "meng" <·······@gmail.com> wrote:
>
> > By the way, LISP has a function `last' which points directly to the
> > last item of a list without needing to traverse it.
>
> No, that's wrong. LAST has to traverse the list and is thus an O(n)
> operation.
>
> We recently had this discussion whether it's possible for an
> ANSI-compliant implementation to internally represent lists in a way
> that would make your behaviour possible. I forgot the outcome but in
> pratice it doesn't matter because all existing Common Lisps do it
> alike.
It seems to me if you want to know the length of the list and rapidly
access the last element you should use a vector instead.
Justin
You want to read Chapter 3 of
"Some Useful Lisp Algorithms: Part 1" at:
http://www.merl.com/publications/TR1991-004/
>From the abstract:
This technical report gathers together three papers that were written
during 1991 and submitted for publication in ACM Lisp Pointers. Each
paper describes a useful Lisp algorithm.
Chapter 1 "Supporting the Regression Testing of Lisp Programs" presents
a system called RT that maintains a database of tests and automatically
runs them when requested. This can take a lot of computer time, but
does not take any of the programmer's time. As a result, any bugs found
by running the tests---and this is a lot more bugs than you might
think---are essentially found for free.
Chapter 2 "Determining the Coverage of a Test Suite" presents a system
called COVER that can help assess the coverage of a suite of test
cases. When a suite of test cases for a program is run in conjunction
with COVER, statistics are kept on which conditions in the code for the
program are exercised and which are not. Based on this information,
COVER can print a report of what has been missed. By devising tests
that exercise these conditions, a programmer can extend the test suite
so that it has more complete coverage.
Chapter 3 "Implementing Queues in Lisp" (co-authored by P.~Norvig)
presents several different algorithms for implementing queues in Lisp.
It discusses why the obvious list-based implementation of queues is
inefficient and the particular situations where more complex
implementations are appropriate.
Glenn
From: Russell McManus
Subject: Re: Decent datastructure for queue operations
Date:
Message-ID: <878xsxwuxo.fsf@cl-user.org>
"meng" <·······@gmail.com> writes:
> - does anyone here have a better idea?
(defclass queue ()
((first-pair :initform nil)
(last-pair :initform nil)))
(defmethod initialize-instance :after ((queue queue)
&key data)
(when data
(with-slots (first-pair last-pair) queue
(setf first-pair data
last-pair (loop for x on data
when (null (cdr x))
return x)))))
(define-condition queue-empty (error)
((queue :initarg :queue :reader queue-empty-queue)))
(defgeneric enqueue (queue datum &optional side)
(:documentation
"Put DATUM in the QUEUE. SIDE can be either :FRONT
or :BACK, by default. Returns DATUM."))
(defmethod enqueue ((queue queue) datum &optional (side :back))
(with-slots (first-pair last-pair) queue
(if (null first-pair)
(setf first-pair (list datum)
last-pair first-pair)
(ecase side
(:back
(let ((new-last-pair (list datum)))
(setf (cdr last-pair) new-last-pair
last-pair new-last-pair)))
(:front
(setf first-pair (cons datum first-pair))))))
datum)
(defgeneric dequeue (queue &optional error-on-empty)
(:documentation
"Returns two values; the value in the queue, and
a flag specifying whether there was a value."))
(defmethod dequeue ((queue queue) &optional (error-on-empty t))
(with-slots (first-pair last-pair) queue
(if (null first-pair)
(if error-on-empty
(error 'queue-empty :queue queue)
(values nil nil))
(let ((v (car first-pair)))
(setf first-pair (cdr first-pair))
(unless first-pair (setf last-pair nil))
(values v t)))))
(defgeneric peek (queue)
(:documentation
"Returns two values; the value in the queue, and
a flag specifying whether there was a value."))
(defmethod peek ((queue queue))
(with-slots (first-pair last-pair) queue
(if (null first-pair)
(values nil nil)
(values (car first-pair) t))))
(defgeneric queue-empty-p (queue))
(defmethod queue-empty-p ((queue queue))
(with-slots (first-pair) queue
(null first-pair)))
(defmethod print-object ((queue queue) stream)
(with-slots (first-pair last-pair) queue
(write `(make-instance 'queue
:data ',first-pair)
:stream stream)))
Thanks Russell for your detailed CLOS code. I will need some time to go
through it :-)
From: Russell McManus
Subject: Re: Decent datastructure for queue operations
Date:
Message-ID: <87zmlcvcbu.fsf@cl-user.org>
"meng" <·······@gmail.com> writes:
> Thanks Russell for your detailed CLOS code. I will need some time to
> go through it :-)
You're welcome. Note that you can subclass my queue class and add a
hash table slot. Then you can intervene in the operations that put
items in the queue to check the hash table, blah blah blah.
-russ
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.
"meng" <·······@gmail.com> writes:
> 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). Binary search has come into mind, but vector is still not a
> good candidate due to difficulty of insertion. Binary search tree might
> be an option, so...
>
> - does anyone here have a better idea?
> - or if a binary search tree is really a great idea, are there built-in
> LISP functions for it?
I can't figure out whether you are talking about a simple queue or a
priority queue.
For a simple queue, you can use a list with a pointer to the last
element (with appropriate use of a sentinel to simplify programming).
If you don't want to use a CONS cell per element, you can use a
circular buffer implemented as a vector, which you would then have to
resize from time to time; or you can use the Flexichain library from
cl.net which already does that for you.
For a priority queue, you need a more sophisticated data structure,
and you cannot get linear (even amortized) complexity of the
operations (as far as I know). The standard implementation uses a
heap which is implemented as a resizable vector. You can also use
other binary trees such as AVL, 2-3, skiplists, etc, but that would
probably be more expensive both in terms of space and time.
--
Robert Strandh
"meng" <·······@gmail.com> writes:
> 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). Binary search has come into mind, but vector is still not a
> good candidate due to difficulty of insertion. Binary search tree might
> be an option, so...
>
> - does anyone here have a better idea?
> - or if a binary search tree is really a great idea, are there built-in
> LISP functions for it?
>
> Thanks in advance for any idea!
Use a queue data structure built on top of lists: keep a reference to
the first and to the last last cons cell. You can google this group
for implementations -- in the case where your queue is just a cons
cell whose car is tht head of the queue and whose cdr is the tail,
this is sometimes called a tconc.
--
/|_ .-----------------------.
,' .\ / | Free Mumia Abu-Jamal! |
,--' _,' | Abolish the racist |
/ / | death penalty! |
( -. | `-----------------------'
| ) |
(`-. '--.)
`. )----'