Could someone tell me where I could read about this topic?
Or where I could see some sample code which implements the
following?
I need to create a QUEUE (a First-In-First-Out structure)
which will handle tens of thousands of characters. I need
to add thousands of characters to the end of this structure
while constantly removing characters from the top of the
structure. I considered implementing this in a list, but
I thought that there would be too much overhead for work
involving characters which are only one byte large.
Any help will be appreciated. Thanks in advance.
..>Raju
In article <·····················@cs.brown.edu> ····@brown.edu (Raju Ramakrishnan) writes:
>Could someone tell me where I could read about this topic?
>Or where I could see some sample code which implements the
>following?
Any algorithms or data structures textbook should have information on queue
implementation techniques. Most of the issues are independent of the
language.
>I need to create a QUEUE (a First-In-First-Out structure)
>which will handle tens of thousands of characters. I need
>to add thousands of characters to the end of this structure
>while constantly removing characters from the top of the
>structure. I considered implementing this in a list, but
>I thought that there would be too much overhead for work
>involving characters which are only one byte large.
If you know an upper bound on the size of the queue, a string would be
best. You would have a head and tail index, and the active elements would
be those after the head and before the tail, wrapping around from the end
of the string to the beginning.
You can also use this even if you don't know the upper bound on the number
of elements, but you can block the transmitter if the queue fills up (i.e.
the tail index catches up to the head index).
If you don't know the maximum and can't block the transmitter, a list is
probably called for. However, it doesn't have to be a list of characters;
as you said, that could be excessive overhead (8 bytes per character in
most implementations). Instead, you could use a list of strings. In this
case, the head and tail indexes would be replaced by references to the list
element and the index into that string. If the strings are length 1000,
the storage overhead of this would be negligible, although it will slow
down accesses to the queue slightly.
--
Barry Margolin
System Manager, Thinking Machines Corp.
······@think.com {uunet,harvard}!think!barmar
In article <·····················@cs.brown.edu> ····@brown.edu (Raju Ramakrishnan) writes:
> I need to create a QUEUE (a First-In-First-Out structure)
> which will handle tens of thousands of characters. I need
> to add thousands of characters to the end of this structure
> while constantly removing characters from the top of the
> structure. I considered implementing this in a list, but
> I thought that there would be too much overhead for work
> involving characters which are only one byte large.
The standard structure for this is what was called in Interlisp a
TCONC list. The idea is to maintain a pointer to the last cell in a
list, as well as the first. ENQUEUE and DEQUEUE are both constant
time operations. A queue of tens of thousdands of characters may
require hundreds of thousdands of bytes of memory (8 bytes/entry in
most CLs), but that shouldn't be a problem on most machines.
(defstruct (queue (:constructor make-queue ()))
head
tail)
(defun enqueue (item queue)
(let ((cell (list item)))
(when (null (queue-head queue))
(setf (queue-head queue) cell))
(setf (queue-tail queue)
(setf (cdr (queue-tail queue)) cell))))
(defun dequeue (queue)
(prog1 (pop (queue-head queue))
(unless (queue-head queue)
(setf (queue-tail queue) '()))))
In article <·····················@cs.brown.edu> ····@brown.edu (Raju Ramakrishnan) writes:
Could someone tell me where I could read about this topic?
Or where I could see some sample code which implements the
following?
I need to create a QUEUE (a First-In-First-Out structure)
which will handle tens of thousands of characters. I need
to add thousands of characters to the end of this structure
while constantly removing characters from the top of the
structure. I considered implementing this in a list, but
I thought that there would be too much overhead for work
involving characters which are only one byte large.
Any help will be appreciated. Thanks in advance.
..>Raju
If you're on Unix you can use a pipe. Here's the C code, you may have
to implement the foreign function interface to pipes yourself.
#include <stdio.h>
main()
{
int fildes[2];
char buf[6];
pipe(fildes); /* Open a pipe. */
write(fildes[1], "Hello", 5); /* Reference the output port of the pipe's file descriptor. */
read(fildes[0], buf, 5); /* Reference the input port of the pipe's file descriptor. */
buf[5] = '\0';
puts(buf); /* Print "Hello\n" on stdout. */
}
--
Patrick Logan, ······@mentorg.com,
Voice: (503) 685-7000 x2907, FAX: (503) 685-1282
Mentor Graphics Corp., Bldg. C, 8005 SW Boeckman Rd., Wilsonville, OR 97070
"Where there is no vision, the people will perish"
In article <·····················@cs.brown.edu> ····@brown.edu (Raju Ramakrishnan) writes:
Path: ·····································@brown.edu
From: ····@brown.edu (Raju Ramakrishnan)
Newsgroups: comp.lang.lisp
Date: 3 Mar 92 17:29:05 GMT
Sender: ····@cs.brown.edu
Distribution: na
Organization: Brown University
Lines: 14
Could someone tell me where I could read about this topic?
Or where I could see some sample code which implements the
following?
I need to create a QUEUE (a First-In-First-Out structure)
which will handle tens of thousands of characters. I need
to add thousands of characters to the end of this structure
while constantly removing characters from the top of the
structure. I considered implementing this in a list, but
I thought that there would be too much overhead for work
involving characters which are only one byte large.
Any help will be appreciated. Thanks in advance.
..>Raju
an alternative for the queue object is a vector, and to use something
like VECTOR-PUSH-EXTEND, which doesn't require you to know how big in
advance, but doesn't complain if you need to overshoot the current
size, because it grows it when necessary.
-- clint
--
Clint Hyde "Give me a LispM or give me death!" -- jwz
Advanced Decision Systems Internet: ·····@chesapeake.ads.com
2111 Wilson Blvd #800
Arlington, VA 22201 (703) 875-0327
In article <··················@pecos.ads.com>, ·····@pecos.ads.com (Clinton Hyde) writes:
|> In article <·····················@cs.brown.edu> ····@brown.edu (Raju Ramakrishnan) writes:
|> I need to create a QUEUE (a First-In-First-Out structure)
|> which will handle tens of thousands of characters. I need
|> to add thousands of characters to the end of this structure
|> while constantly removing characters from the top of the
|> structure. I considered implementing this in a list, but
|> I thought that there would be too much overhead for work
|> involving characters which are only one byte large.
Let the compiler worry about the overhead ;-)
This sounds like an ideal application for the old Interlisp TCONC function. We build a list from left to right by adding elements onto the end of a 'pointer'. The regular list can be retrieved from the CAR of the pointer at any time.
(defun tconc (ptr x)
(setq x (list x))
(cond (ptr
(cond ((car ptr)
(when x
(setf (cdr (cdr ptr)) x)
(setf (cdr ptr) x)))
(t
(setf (car ptr) x)
(setf (cdr ptr) x))))
(t
(setq ptr (tcons x))))
ptr)
;;create a pointer to be used by TCONC
(defun tcons (&optional list)
(cons list (last list)))
..................................................
Len Charest, Jr.
JPL Artificial Intelligence Group
·······@aig.jpl.nasa.gov