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>