Services & ResourcesWolfram ForumsMathGroup Archive

[Date Index] [Thread Index] [Author Index]

Re: is there really no efficient way to delete an element from a list??

• To: mathgroup at smc.vnet.net
• Subject: [mg24190] Re: [mg23925] is there really no efficient way to delete an element from a list??
• From: Daniel Lichtblau <danl at wolfram.com>
• Date: Wed, 28 Jun 2000 22:51:10 -0400 (EDT)
• References: <200006160457.AAA09836@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

Martin Bauer wrote:
> 
> hi, i tried to implement a queue with mathematica;
> is it possible that there is no O(1) way to get
> queue = Rest[queue]  ??
> 
> it seems that mathematica uses call by value instead of call by reference
> here;
> i know that there are PrependTo[] and ApendTo[] for building the list; is
> there any equivalent to these functions to remove elements?
> 
> or is there another way to implement a stack or queue with constant time
> access?
> 
> --martin.
> 
> ----------------------------------------------------------------------------
> Martin Bauer                          email:  martin.bauer at in.tum.de
> Department of Computer Science          www:  http://www.in.tum.de/~bauerma
> Technische Universitat Munchen          tel:  +49-89-289-25724
> D-80290 Munchen, Germany               room:  3202  main bldg, Arcisstr.21
> ----------------------------------------------------------------------------

You can emulate call-by-reference using HoldXXX attributes. This is used
below in the stack and queue implementations. Stacks are easy so we'll
do that first. One way is to use a Mathematica List, nesting each time
we push a new element.

SetAttributes[push, HoldFirst]
push[stack_, elem_] := stack = {elem, stack}

SetAttributes[pop, HoldFirst]
pop[{}] := (Print["Stack is empty"]; Null)
pop[stack_] := With[{elem = First[stack]},
    stack = Last[stack]; elem]

emptyStack[stack_] := stack == {}


Simple example:

In[23]:= myStack = {};

In[24]:= Do[push[myStack,j^2], {j,10}]

In[25]:= myStack
Out[25]= {100, {81, {64, {49, {36, {25, {16, {9, {4, {1, {}}}}}}}}}}}

In[26]:= k = 0;

In[27]:= While [!emptyStack[myStack], k++; Print[pop[myStack]]]
100
81
64
49
36
25
16
9
4
1

In[28]:= k
Out[28]= 10


For queues we need to implement first-in-first-out (FIFO), and this is
trickier given that we require constant time to add and remove elements.
One method is to use a fixed size table and have front and back indices
that wrap around. We add at the front and remove at the back. We require
routines to
(i) get a new queue
(ii) Check the length and in particular check if it is empty (could also
have a check-for-full-queue function).
(iii) add elements
(iv) remove elements


qelems = 1; qlen = 2; qsize = 3; qfront = 4; qback = 5;

newQueue[len_Integer] /; len>0 := {Table[0,{len}], 0, len, 1, 1}

emptyQueue[Q_] := Q[[qlen]] == 0

queueLength[Q_] := Q[[qlen]]

SetAttributes[enQueue, HoldFirst]
enQueue[Q_, elem_] :=
	If [Q[[qlen]] == Q[[qsize]], Print["Queue is full"],
		Q[[qlen]]++;
		Q[[qelems,Q[[qfront]]]] = elem;
		Q[[qfront]] = Mod[Q[[qfront]]+1,Q[[qsize]],1];
		]

SetAttributes[deQueue, HoldFirst]
deQueue[Q_] /; emptyQueue[Q] := Null
deQueue[Q_] := (
	Q[[qlen]]--;
	Q[[qback]] = Mod[Q[[qback]]+1,Q[[qsize]],1];
	Q[[qelems, Mod[Q[[qback]]-1,Q[[qsize]],1]]]
	)

Another simple example:

In[42]:= myQ = newQueue[7];

In[43]:= Map[enQueue[myQ,#]&, {"Hello Dolly", "West Side Story"}];

In[44]:= queueLength[myQ]
Out[44]= 2

In[45]:= show1 = deQueue[myQ]
Out[45]= Hello Dolly

In[46]:= Map[enQueue[myQ,#]&, {"My Fair Lady", "Les Miz", "Phantom",
	"Fiddler", "Mouse Trap", "Rent", "Sleuth"}];
Queue is full

In[47]:= show2 = deQueue[myQ]
Out[47]= West Side Story

In[48]:= enQueue[myQ,"Sleuth"]

If you do not want to work with a fixed size queue you can still get
constant time adding/removing using sparse functions ("memo-ization").
Below is some code I cribbed from a 1999 Developer Conference notebook.
It uses first and last rather than front and back for denoting where we
add and remove. Also we have no need to "wrap around" the indices; both
simply keep growing. We keep a field around to store the current entry
at the back (the next one to be removed) just to avoid using a local
variable in a With or Module. We also require a symbol to give to
newQueue. It determines where we attach down-values for queue entries.

Clear[enQueue, deQueue, newQueue, queueLength]

qptr = 1; qlen = 2; qfirst = 3; qlast = 4; qelem = 5;

newQueue[sym_Symbol] := {Unique[sym], 0, 0, 0, Null}

emptyQueue[Q_] := Q[[qlen]] == 0

SetAttributes[enQueue, HoldFirst]
enQueue[Q_, elem_] := (
	Q[[qlen]]++;
	Q[[qfirst]]++; 
	Q[[qptr]][Q[[qfirst]]] = elem;
	)

SetAttributes[deQueue, HoldFirst]
deQueue[Q_] := (
	Q[[qlen]]--;
	Q[[qlast]]++;
	Q[[qelem]] = Q[[qptr]][Q[[qlast]]]; 
	Q[[qptr]][Q[[qlast]]] =.;
	Q[[qelem]]
	)

Previous example, revisited.

In[73]:= myQ = newQueue[qq];

In[74]:= Map[enQueue[myQ,#]&, {"Hello Dolly", "West Side Story"}];

In[75]:= queueLength[myQ]
Out[75]= 2

In[76]:= show1 = deQueue[myQ]
Out[76]= Hello Dolly

In[77]:= Map[enQueue[myQ,#]&, {"My Fair Lady", "Les Miz", "Phantom",
"Fiddler",
        "Mouse Trap", "Rent", "Sleuth"}];
         
In[78]:= queueLength[myQ]
Out[78]= 8

In[79]:= show1 = deQueue[myQ]
Out[79]= West Side Story

Note that we only use the memory we need, in that we clear entries for
elements removed via deQueue.

The drawback to this method is that, while the various operations are
all O(1), the implied constant is large due to a need to store and look
up values in an internal hash table. As an internal detail, this table
can grow when buckets get crowded, hence a given enQueue might be O(n),
but the average time is O(1).

One might hybridize these approaches to get the faster access associated
with a fixed-size array, combined with the "unlimited" size associated
with sparse functions (the actual salient feature is that they use only
the memory they need; we could after all preallocate an unrealistically
large table for the first method). This hybridization can be
accomplished by, say, doubling the size of the table every time the
queue gets full, copying over the entries already on it. Again we
sometimes have an O(n) addition, but the average is O(1). If so desired,
one can get more subtle with memory management and allow for the queue
table to shrink (say by 1/2) whenever the fraction of entries falls
below some threshhold, e.g 1/3, of the capacity; this again can help to
avoid wasting space in cases of once-large queues that have shrunk
considerably. So long as fixed ratios are used it is not hard to show
that average time for enQueue/deQueue will be O(1) even though
occasionally such an operation is O(n).


Daniel Lichtblau
Wolfram Research

• References:
  • is there really no efficient way to delete an element from a list??
    • From: Martin Bauer <b@hcii.de>