From: Christopher R. Barry
Subject: What's a good queue that allows any item to be dropped?
Date:
Message-ID: <87d7plol9e.fsf@2xtreme.net>
I've been writing a program and just realized that I will sometimes
have to delete something from a queue that could be in any position
within the queue. (I will never need to do a non-first-in insertion,
however.) I've been using basically the Graham-style implementation of
queues where you start with (NIL . NIL) and have the cdr point to the
last cons of the car of the queue.
I'm thinking I should go with a doubly-linked list queue
implementation, but I thought I'd just ask here first rather than
spend my time to think of something probably not as good.
Christopher
······@2xtreme.net (Christopher R. Barry) writes:
> I've been writing a program and just realized that I will sometimes
> have to delete something from a queue that could be in any position
> within the queue. (I will never need to do a non-first-in insertion,
> however.) I've been using basically the Graham-style implementation of
> queues where you start with (NIL . NIL) and have the cdr point to the
> last cons of the car of the queue.
>
> I'm thinking I should go with a doubly-linked list queue
> implementation, but I thought I'd just ask here first rather than
> spend my time to think of something probably not as good.
A doubly linked list will make the delete operation linear, which may
or may not be a problem to you. If you can accept that delete
always take linear time, you can also use a singly linked list. Just
insert at the front of the list, and use one of the existing delete
functions to delete from the queue.
How will you indicate the element to be deleted? By position or by
some comparison?
--
Robert Strandh
---------------------------------------------------------------------
Greenspun's Tenth Rule of Programming: any sufficiently complicated C
or Fortran program contains an ad hoc informally-specified bug-ridden
slow implementation of half of Common Lisp.
---------------------------------------------------------------------
From: Roger Corman
Subject: Re: What's a good queue that allows any item to be dropped?
Date:
Message-ID: <38b6d441.65051228@nntp.best.com>
On 25 Feb 2000 11:15:54 +0100, Robert STRANDH
<·······@napperon.labri.u-bordeaux.fr> wrote:
>······@2xtreme.net (Christopher R. Barry) writes:
>
>> I've been writing a program and just realized that I will sometimes
>> have to delete something from a queue that could be in any position
>> within the queue. (I will never need to do a non-first-in insertion,
>> however.) I've been using basically the Graham-style implementation of
>> queues where you start with (NIL . NIL) and have the cdr point to the
>> last cons of the car of the queue.
>>
>> I'm thinking I should go with a doubly-linked list queue
>> implementation, but I thought I'd just ask here first rather than
>> spend my time to think of something probably not as good.
>
>A doubly linked list will make the delete operation linear, which may
>or may not be a problem to you. If you can accept that delete
>always take linear time, you can also use a singly linked list. Just
>insert at the front of the list, and use one of the existing delete
>functions to delete from the queue.
>
>How will you indicate the element to be deleted? By position or by
>some comparison?
>
>--
If he already has the object, and just want to remove it from the
queue (which is often the case) then the doubly-linked list is the
most efficient approach, since it would require constant time to
unlink it. If a lookup is required, I don't think a doubly-linked list
adds any value, since, as Robert pointed out, the best you can do is
linear time and the delete operator will give you that with a singly
linked list.
Roger Corman
From: Barry Margolin
Subject: Re: What's a good queue that allows any item to be dropped?
Date:
Message-ID: <JPAt4.63$I31.1486@burlma1-snr2>
In article <·················@nntp.best.com>,
Roger Corman <·····@xippix.com> wrote:
>If he already has the object, and just want to remove it from the
>queue (which is often the case) then the doubly-linked list is the
>most efficient approach, since it would require constant time to
When you say "the object", it seems like you're referring to the backbone
object, not the entry in the queue.
>unlink it. If a lookup is required, I don't think a doubly-linked list
>adds any value, since, as Robert pointed out, the best you can do is
>linear time and the delete operator will give you that with a singly
>linked list.
Just remember that as you're scanning, you need to remember the previous
backbone element. Because if you remove the last element in the list, you
have to update the "last element" pointer in the container object.
--
Barry Margolin, ······@bbnplanet.com
GTE Internetworking, Powered by BBN, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
From: Robert Strandh
Subject: Re: What's a good queue that allows any item to be dropped?
Date:
Message-ID: <6wvh3dhre8.fsf@labri.u-bordeaux.fr>
Barry Margolin <······@bbnplanet.com> writes:
> Just remember that as you're scanning, you need to remember the previous
> backbone element. Because if you remove the last element in the list, you
> have to update the "last element" pointer in the container object.
If it is acceptable that all delete operations take linear time, you
don't need a "last element" pointer. You insert elements at the front
of the list, and remove them with some existing linear delete
operation.
--
Robert Strandh
---------------------------------------------------------------------
Greenspun's Tenth Rule of Programming: any sufficiently complicated C
or Fortran program contains an ad hoc informally-specified bug-ridden
slow implementation of half of Common Lisp.
---------------------------------------------------------------------
From: Barry Margolin
Subject: Re: What's a good queue that allows any item to be dropped?
Date:
Message-ID: <D5Ft4.85$I31.2058@burlma1-snr2>
In article <··············@labri.u-bordeaux.fr>,
Robert Strandh <·······@labri.u-bordeaux.fr> wrote:
>Barry Margolin <······@bbnplanet.com> writes:
>
>> Just remember that as you're scanning, you need to remember the previous
>> backbone element. Because if you remove the last element in the list, you
>> have to update the "last element" pointer in the container object.
>
>If it is acceptable that all delete operations take linear time, you
>don't need a "last element" pointer. You insert elements at the front
>of the list, and remove them with some existing linear delete
>operation.
I think the expectation for a queue would be that the FIFO operations
should be constant time. Only random-access dropping should require linear
time.
--
Barry Margolin, ······@bbnplanet.com
GTE Internetworking, Powered by BBN, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
Two suggestions that might help, depending on what you are trying to
achieve:
Sometimes it can be useful to mark an object as deleted rather than
actually deleting it.
Then, when your "dequeue" operation sees it, it passes on to the next
element.
E.g. If you have a queue of "things to do, and when to do them", you
could update the "thing to do" to "do nothing".
Another thought: Maybe you can somehow delay the test causing the
deletion to when the object is about to be dequeued anyhow?
I don't know if this helped, but it sometimes helps to look at a
problem from a totally new angle.
Stig Hemmer,
Jack of a Few Trades.
From: Christopher R. Barry
Subject: OT: Problem solving and trying new angles. (was Re: What's a good queue that allows any item to be dropped?)
Date:
Message-ID: <87wvnoheqz.fsf_-_@2xtreme.net>
Stig Hemmer <····@verden.pvv.ntnu.no> writes:
[...]
> I don't know if this helped, but it sometimes helps to look at a
> problem from a totally new angle.
Indeed; I've been learning much about this with mathematics and proof
lately. I remember reading that psychologists who have studied problem
solving have found that the most successful problem solvers are those
who are flexible and willing to use a variety of approaches without
getting stuck in any one of them for very long. I don't have a
reference for this. (And I posted this reply hoping someone would read
it that had more information.)
Christopher
From: Sashank Varma
Subject: Re: OT: Problem solving and trying new angles. (was Re: What's a good queue that allows any item to be dropped?)
Date:
Message-ID: <sashank-2902001004320001@129.59.212.53>
In article <·················@2xtreme.net>, ······@2xtreme.net
(Christopher R. Barry) wrote:
[snip]
>Indeed; I've been learning much about this with mathematics and proof
>lately. I remember reading that psychologists who have studied problem
>solving have found that the most successful problem solvers are those
>who are flexible and willing to use a variety of approaches without
>getting stuck in any one of them for very long. I don't have a
>reference for this. (And I posted this reply hoping someone would read
>it that had more information.)
[snip]
this isn't quite my area of cognitive psychology, but a few thoughts
come to mind:
(1) there's a tradition of problem solving research that give people
trick ("insight") problems, where the surface structures suggests
certain constraints and solution paths that in fact turn out to
be wrong. it requires a willingness to break constraints and
try novel strategies to solve these problems. this work started
with the gestalt folks (wertheimer) in the first half of the
twentieth century. their general view was that you first attack
a problem and then fail. you then walk around for a while
thinking about other things ("incubating") until, in a flash of
insight, you see a solution. a related idea is that to solve
hard problems, you must break "set," or your initial bias. i could
give more detail on these studies and psychological concepts if
you're interested.
(2) one could view the standard problem-solving-as-heuristic-search
approach as positing multiple strategies -- if one path and/or
(pun intended) goal decomposition doesn't work, try another.
or, if you hit a local maximum in the search space, you might
need to try another strategy to escape it. (or "turn the
temperature up," to use another metaphor.)
(3) some of the more applied approaches to problem solving, at the
interface of cognitive science and education, have found that
the number of strategies a student is willing to try predicts
future success in at least some domains of high school math.
check out ken koedinger's work at carnegie mellon (he's in the
hci department) for references to this and other work of
interest -- math tutors developed in lisp *that really work*.
sashank
From: Sashank Varma
Subject: Re: OT: Problem solving and trying new angles. (was Re: What's a good queue that allows any item to be dropped?)
Date:
Message-ID: <sashank-2902001022330001@129.59.212.53>
In article <························@129.59.212.53>,
·······@vuse.vanderbilt.edu (Sashank Varma) wrote:
[snip]
>(1) there's a tradition of problem solving research that give people
> trick ("insight") problems, where the surface structures suggests
> certain constraints and solution paths that in fact turn out to
> be wrong. it requires a willingness to break constraints and
> try novel strategies to solve these problems. this work started
> with the gestalt folks (wertheimer) in the first half of the
> twentieth century. their general view was that you first attack
> a problem and then fail. you then walk around for a while
> thinking about other things ("incubating") until, in a flash of
> insight, you see a solution. a related idea is that to solve
> hard problems, you must break "set," or your initial bias. i could
> give more detail on these studies and psychological concepts if
> you're interested.
[snip]
argh. one more thing. you mentioned that you have been learning a
bit about mathematics and proof recently. you should definitely
check out jacques hadamard's "the psychology of invention in the
mathematical fiedl: how creativity is tapped in science; the
unconsciousness mind and discovery; intuition vs. verbal reasoning;
poincare's forgetting hypothesis; creative techniques of einstein;
pascal, wiener, and others."
(the title reads like a fiona apple cd...)
it's a short introspective work by an eminent mathematician on
his creative process that draws heavily from gestalt problem
solving ideas. it's one of those books you find a lot of
mathematically inclined folks have read, much like more biologists
than you'd expect by chance have stumbled upon d'arcy wentworth
thompson's "on growth and form."
sashank