Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #910 > unrolled thread

Understanding Sequential Allocation - Knuth TAoCP

Back to article view | Back to comp.programming

Contents

  Understanding Sequential Allocation - Knuth TAoCP arnuld <sunrise@invalid.address> - 2011-10-10 14:38 +0000
    Re: Understanding Sequential Allocation - Knuth TAoCP Azazel <azazel@remove.azazel.net> - 2011-10-10 10:21 -0500
      Re: Understanding Sequential Allocation - Knuth TAoCP arnuld <sunrise@invalid.address> - 2011-10-13 12:27 +0000
        Re: Understanding Sequential Allocation - Knuth TAoCP Ike Naar <ike@sverige.freeshell.org> - 2011-10-13 14:06 +0000
          Re: Understanding Sequential Allocation - Knuth TAoCP arnuld <sunrise@invalid.address> - 2011-10-17 11:48 +0000
            Re: Understanding Sequential Allocation - Knuth TAoCP Ike Naar <ike@sverige.freeshell.org> - 2011-10-17 22:28 +0000
              Re: Understanding Sequential Allocation - Knuth TAoCP "io_x" <a@b.c.invalid> - 2011-10-20 10:22 +0200
                Re: Understanding Sequential Allocation - Knuth TAoCP "io_x" <a@b.c.invalid> - 2011-10-20 14:14 +0200
    Re: Understanding Sequential Allocation - Knuth TAoCP Patricia Shanahan <pats@acm.org> - 2011-10-10 09:58 -0700
      Re: Understanding Sequential Allocation - Knuth TAoCP arnuld <sunrise@invalid.address> - 2011-10-17 11:41 +0000
    Re: Understanding Sequential Allocation - Knuth TAoCP Robin Vowels <robin.vowels@gmail.com> - 2011-10-16 17:24 -0700

#910 — Understanding Sequential Allocation - Knuth TAoCP

This is from Knuth's TAoCP Volume 1, section 2.2.2 - Sequential 
Allocation, which I am unable to understand:


---- Knuth begins ----

The representation of a queue or  more general  deque is a little 
trickier. An obvious solution is to keep two pointers, say F and R (for 
the front and rear of the queue), with F = R = 0 when the queue is empty. 
Then inserting an element at the rear of the queue would be:

 R <-- R + 1;   X[R] <-- Y.       

Removing the front node(F points just below the front) would be:

 F <-- F + 1;   Y <-- X[F];    if F = R, then set F <-- R <-- 0.


.. SNIP Knuth a bit here..

To circumvent the problem of the queue overrunning memory, we can set 
aside M nodes X[1]...X[M] arranged implicitly in a circle with X[1] 
following X[M]. Then above equations become:


 if R = M then R <-- 1,  otherwise R <-- R + 1;   X[R] <-- Y
 if F = M then F <-- 1,  otherwise F <-- F + 1;   Y <-- X[F] 

---- Knuth ends  ----


I did not understand that how you can say F = F + 1 when you remove an 
item/node/element from the sequential allocation (e.g. array in C ?). The 
front always points to front and rear always points to rear, the values 
inside them may change but front is always a front e.g. if X is a C array 
then:

 X[0]  is always front, no matter what value it has, same for rear. How 
can you say X[1] is front ? 

Can someone please explain ?



-- 
 arnuld
http://LispMachine.Wordpress.com

[toc] | [next] | [standalone]

#911

On 2011-10-10, arnuld <sunrise@invalid.address> wrote:
> ---- Knuth begins ----
>
> The representation of a queue or  more general  deque is a little
> trickier. An obvious solution is to keep two pointers, say F and R
> (for
> the front and rear of the queue), with F = R = 0 when the queue is
> empty.
> Then inserting an element at the rear of the queue would be:
>
>  R <-- R + 1;   X[R] <-- Y.
>
> Removing the front node(F points just below the front) would be:
>
>  F <-- F + 1;   Y <-- X[F];    if F = R, then set F <-- R <-- 0.
>
> ---- Knuth ends  ----
>
>
> I did not understand that how you can say F = F + 1 when you remove an
> item/node/element from the sequential allocation (e.g. array in C ?).
> The front always points to front and rear always points to rear, the
> values inside them may change but front is always a front e.g. if X is
> a C array then:
>
> X[0] is always front, no matter what value it has, same for rear.
> How can you say X[1] is front ?
>
> Can someone please explain ?

In C terms, the queue is an array of arbitrary length, and F and R are
indices which point to the current front and rear elements.  When we
dequeue the first element, we do this by incrementing the index F;
when we queue an element at the end we do this by incrementing the index
R.

Start:

  +-+-+-+-+-+-+
  | | | | | | |
  +-+-+-+-+-+-+
   F = 0
   R = 0

Queue (insert at R; increment R):

  +-+-+-+-+-+-+
  |1| | | | | |
  +-+-+-+-+-+-+
   F = 0
     R = 1

Queue (insert at R; increment R):

  +-+-+-+-+-+-+
  |1|2| | | | |
  +-+-+-+-+-+-+
   F = 0
       R = 2

Dequeue (remove from F; increment F; if F == R then F = R = 0):

  +-+-+-+-+-+-+
  | |2| | | | |
  +-+-+-+-+-+-+
     F = 1
       R = 2

Queue (insert at R; increment R):

  +-+-+-+-+-+-+
  | |2|3| | | |
  +-+-+-+-+-+-+
     F = 1
	 R = 3

Dequeue (remove from F; increment F; if F == R then F = R = 0):

  +-+-+-+-+-+-+
  | | |3| | | |
  +-+-+-+-+-+-+
       F = 2
	 R = 3

Dequeue (remove from F; increment F; if F == R then F = R = 0):

  +-+-+-+-+-+-+
  | | | | | | |
  +-+-+-+-+-+-+
   F = 0
   R = 0

In the bit I snipped Knuth explains how to avoid running of the end
of the array by wrapping the indices.

J.
-- 
Az.

[toc] | [prev] | [next] | [standalone]

#918

> > On Mon, 10 Oct 2011 10:21:24 -0500, Azazel wrote:

> ..SNIP...

> Start:
> 
>   +-+-+-+-+-+-+
>   | | | | | | |
>   +-+-+-+-+-+-+
>    F = 0
>    R = 0
> 
> Queue (insert at R; increment R):
> 
>   +-+-+-+-+-+-+
>   |1| | | | | |
>   +-+-+-+-+-+-+
>    F = 0
>      R = 1

I thought that when a Queue has only one element then both front and rear 
(or head and tail) point to same element (from my practical experience of 
writing many Queues in C). What I am missing here ?


 

> ..SNIP..

> Dequeue (remove from F; increment F; if F == R then F = R = 0):
> 
>   +-+-+-+-+-+-+
>   | | |3| | | |
>   +-+-+-+-+-+-+
>        F = 2
> 	 R = 3
 
> Dequeue (remove from F; increment F; if F == R then F = R = 0):
> 
>   +-+-+-+-+-+-+
>   | | | | | | |
>   +-+-+-+-+-+-+
>    F = 0
>    R = 0


Both F and R, in one step, become 0 (zero) from F = 2 and R = 3. F and R 
point to indexes in array ?




-- 
 arnuld
http://LispMachine.Wordpress.com

[toc] | [prev] | [next] | [standalone]

#919

On 2011-10-13, arnuld <sunrise@invalid.address> wrote:
>> Queue (insert at R; increment R):
>> 
>>   +-+-+-+-+-+-+
>>   |1| | | | | |
>>   +-+-+-+-+-+-+
>>    F = 0
>>      R = 1
>
> I thought that when a Queue has only one element then both front and rear 
> (or head and tail) point to same element (from my practical experience of 
> writing many Queues in C). What I am missing here ?

Let's re-quote your Knuth quote:

# Then inserting an element at the rear of the queue would be:
# 
#  R <-- R + 1;   X[R] <-- Y.
# 
# Removing the front node(F points just below the front) would be:
# 
#  F <-- F + 1;   Y <-- X[F];    if F = R, then set F <-- R <-- 0.

so R points *to* the rear, F points *just below* the front.

So, if the queue has one element, R points to it,
and F points just below it.

     ---+---+---+---+---
        |   | X |   |
     ---+---+---+---+---
          ^   ^
          F   R

Of course one can define the front and rear pointers in another
way; like in your experience, the front pointer can point
*to* the front element, and the rear pointer can point *to* the
rear element. If you follow that convention, then, indeed, for
a queue that contains one element, front and rear point to that
element.

     ---+---+---+---+---
        |   | X |   |
     ---+---+---+---+---
              ^
             F=R

Yet another convention is to let the front pointer point *to*
the front element, and let the rear pointer point *just after*
the rear element. Then the front and rear pointers are, just like
in Knuth's case, not the same for a queue that contains a
single element.

     ---+---+---+---+---
        |   | X |   |
     ---+---+---+---+---
              ^   ^
              F   R

[toc] | [prev] | [next] | [standalone]

#930

> > On Thu, 13 Oct 2011 14:06:29 +0000, Ike Naar wrote:


> Let's re-quote your Knuth quote:
> 
> # Then inserting an element at the rear of the queue would be: #
> #  R <-- R + 1;   X[R] <-- Y.
> #
> # Removing the front node(F points just below the front) would be: #
> #  F <-- F + 1;   Y <-- X[F];    if F = R, then set F <-- R <-- 0.
> 
> so R points *to* the rear, F points *just below* the front.

> So, if the queue has one element, R points to it, and F points just
> below it.
> 
>      ---+---+---+---+---
>         |   | X |   |
>      ---+---+---+---+---
>           ^   ^
>           F   R


I don't see any above or below in array (may be our definitions are 
different). I see just before or after an element and array index. e.g. 
if array has one element then R points to first element (at index 0 in a 
C array) while F points where ? , in between index 0 and 1 ? and how its 
feasible ?

 
 
> Of course one can define the front and rear pointers in another way;
> like in your experience, the front pointer can point *to* the front
> element, and the rear pointer can point *to* the rear element. If you
> follow that convention, then, indeed, for a queue that contains one
> element, front and rear point to that element.
> 
>      ---+---+---+---+---
>         |   | X |   |
>      ---+---+---+---+---
>               ^
>              F=R
> 
> Yet another convention is to let the front pointer point *to* the front
> element, and let the rear pointer point *just after* the rear element.
> Then the front and rear pointers are, just like in Knuth's case, not the
> same for a queue that contains a single element.
> 
>      ---+---+---+---+---
>         |   | X |   |
>      ---+---+---+---+---
>               ^   ^
>               F   R


Okay, you mean that you can use several different methods for pointing to 
head/tail of a Queue ? And Knuth uses one which suits him ?  And other 
books will use different methods to create the Queue ? and all of them 
are right ?





-- 
 arnuld
http://LispMachine.Wordpress.com

[toc] | [prev] | [next] | [standalone]

#935

On 2011-10-17, arnuld <sunrise@invalid.address> wrote:
>> > On Thu, 13 Oct 2011 14:06:29 +0000, Ike Naar wrote:
>
>
>> Let's re-quote your Knuth quote:
>> 
>> # Then inserting an element at the rear of the queue would be: #
>> #  R <-- R + 1;   X[R] <-- Y.
>> #
>> # Removing the front node(F points just below the front) would be: #
>> #  F <-- F + 1;   Y <-- X[F];    if F = R, then set F <-- R <-- 0.
>> 
>> so R points *to* the rear, F points *just below* the front.
>
>> So, if the queue has one element, R points to it, and F points just
>> below it.
>> 
>>      ---+---+---+---+---
>>         |   | X |   |
>>      ---+---+---+---+---
>>           ^   ^
>>           F   R
>
> I don't see any above or below in array (may be our definitions are 
> different). I see just before or after an element and array index. e.g. 
> if array has one element then R points to first element (at index 0 in a 
> C array) while F points where ? , in between index 0 and 1 ? and how its 
> feasible ?

Start with an empty queue, F = R = 0

     +---+---+---+---+---
     |   |   |   |   |
     +---+---+---+---+---
       0   1   2   3   4
      F=R

Insert an element 'A' (at the rear), R <- R+1, X[R] <- 'A'

     +---+---+---+---+---
     |   | A |   |   |
     +---+---+---+---+---
       0   1   2   3   4
       F   R

Insert an element 'B' (at the rear), R <- R+1, X[R] <- 'B'

     +---+---+---+---+---
     |   | A | B |   |
     +---+---+---+---+---
       0   1   2   3   4
       F       R

Insert an element 'C' (at the rear), R <- R+1, X[R] <- 'C'

     +---+---+---+---+---
     |   | A | B | C |
     +---+---+---+---+---
       0   1   2   3   4
       F           R

Remove the front node (the 'A'),
F <- F + 1, Y <-- X[F]; if F = R, then set F <-- R <-- 0.

     +---+---+---+---+---
     |   |   | B | C |
     +---+---+---+---+---
       0   1   2   3   4
           F       R

Insert an element 'D' (at the rear), R <- R+1, X[R] <- 'D'

     +---+---+---+---+---
     |   |   | B | C | D
     +---+---+---+---+---
       0   1   2   3   4
           F           R

Remove the front node (the 'B'),
F <- F + 1, Y <-- X[F]; if F = R, then set F <-- R <-- 0.

     +---+---+---+---+---
     |   |   |   | C | D
     +---+---+---+---+---
       0   1   2   3   4
               F       R

[toc] | [prev] | [next] | [standalone]

#942

"Ike Naar" <ike@sverige.freeshell.org> ha scritto nel messaggio
news:slrn3vfsj9pb0h.q1u.ike@sverige.freeshell.org...
> On 2011-10-17, arnuld <sunrise@invalid.address> wrote:
>>> > On Thu, 13 Oct 2011 14:06:29 +0000, Ike Naar wrote:
>>
>>
>>> Let's re-quote your Knuth quote:
>>>
>>> # Then inserting an element at the rear of the queue would be: #
>>> #  R <-- R + 1;   X[R] <-- Y.
>>> #
>>> # Removing the front node(F points just below the front) would be: #
>>> #  F <-- F + 1;   Y <-- X[F];    if F = R, then set F <-- R <-- 0.
>>>
>>> so R points *to* the rear, F points *just below* the front.
>>
>>> So, if the queue has one element, R points to it, and F points just
>>> below it.
>>>
>>>      ---+---+---+---+---
>>>         |   | X |   |
>>>      ---+---+---+---+---
>>>           ^   ^
>>>           F   R
>>
>> I don't see any above or below in array (may be our definitions are
>> different). I see just before or after an element and array index. e.g.
>> if array has one element then R points to first element (at index 0 in a
>> C array) while F points where ? , in between index 0 and 1 ? and how its
>> feasible ?
>
> Start with an empty queue, F = R = 0
>
>     +---+---+---+---+---
>     |   |   |   |   |
>     +---+---+---+---+---
>       0   1   2   3   4
>      F=R
>
> Insert an element 'A' (at the rear), R <- R+1, X[R] <- 'A'
>
>     +---+---+---+---+---
>     |   | A |   |   |
>     +---+---+---+---+---
>       0   1   2   3   4
>       F   R
>
> Insert an element 'B' (at the rear), R <- R+1, X[R] <- 'B'
>
>     +---+---+---+---+---
>     |   | A | B |   |
>     +---+---+---+---+---
>       0   1   2   3   4
>       F       R
>
> Insert an element 'C' (at the rear), R <- R+1, X[R] <- 'C'
>
>     +---+---+---+---+---
>     |   | A | B | C |
>     +---+---+---+---+---
>       0   1   2   3   4
>       F           R
>
> Remove the front node (the 'A'),
> F <- F + 1, Y <-- X[F]; if F = R, then set F <-- R <-- 0.
>
>     +---+---+---+---+---
>     |   |   | B | C |
>     +---+---+---+---+---
>       0   1   2   3   4
>           F       R

in base to what you write of above example
the queue would be afther
"Remove the front node (the 'A'),"


     +---+---+---+---+---
     |   | A | B | C |
     +---+---+---+---+---
       0   1   2   3   4
           F       R

this would be one static [one fixed len array base]
implementation of a queue

i don't understand well why there is the need of the operation:
if F = R, then set F <-- R <-- 0.

why the queue has to start to indexes F=R=0?
and not start to F=R=1 index [using modulo array size operations]

because if F==R whould mean queue is void... right?

> Insert an element 'D' (at the rear), R <- R+1, X[R] <- 'D'
>
>     +---+---+---+---+---
>     |   |   | B | C | D
>     +---+---+---+---+---
>       0   1   2   3   4
>           F           R
>
> Remove the front node (the 'B'),
> F <- F + 1, Y <-- X[F]; if F = R, then set F <-- R <-- 0.
>
>     +---+---+---+---+---
>     |   |   |   | C | D
>     +---+---+---+---+---
>       0   1   2   3   4
>               F       R

[toc] | [prev] | [next] | [standalone]

#943

"io_x" <a@b.c.invalid> ha scritto nel messaggio 
news:4e9fd98f$0$1392$4fafbaef@reader1.news.tin.it...
>
> "Ike Naar" <ike@sverige.freeshell.org> ha scritto nel messaggio
> news:slrn3vfsj9pb0h.q1u.ike@sverige.freeshell.org...
>> On 2011-10-17, arnuld <sunrise@invalid.address> wrote:
>>>> > On Thu, 13 Oct 2011 14:06:29 +0000, Ike Naar wrote:
>>>
>>>
>>>> Let's re-quote your Knuth quote:
>>>>
>>>> # Then inserting an element at the rear of the queue would be: #
>>>> #  R <-- R + 1;   X[R] <-- Y.
>>>> #
>>>> # Removing the front node(F points just below the front) would be: #
>>>> #  F <-- F + 1;   Y <-- X[F];    if F = R, then set F <-- R <-- 0.
>>>>
>>>> so R points *to* the rear, F points *just below* the front.
>>>
>>>> So, if the queue has one element, R points to it, and F points just
>>>> below it.
>>>>
>>>>      ---+---+---+---+---
>>>>         |   | X |   |
>>>>      ---+---+---+---+---
>>>>           ^   ^
>>>>           F   R
>>>
>>> I don't see any above or below in array (may be our definitions are
>>> different). I see just before or after an element and array index. e.g.
>>> if array has one element then R points to first element (at index 0 in a
>>> C array) while F points where ? , in between index 0 and 1 ? and how its
>>> feasible ?
>>
>> Start with an empty queue, F = R = 0
>>
>>     +---+---+---+---+---
>>     |   |   |   |   |
>>     +---+---+---+---+---
>>       0   1   2   3   4
>>      F=R
>>
>> Insert an element 'A' (at the rear), R <- R+1, X[R] <- 'A'
>>
>>     +---+---+---+---+---
>>     |   | A |   |   |
>>     +---+---+---+---+---
>>       0   1   2   3   4
>>       F   R
>>
>> Insert an element 'B' (at the rear), R <- R+1, X[R] <- 'B'
>>
>>     +---+---+---+---+---
>>     |   | A | B |   |
>>     +---+---+---+---+---
>>       0   1   2   3   4
>>       F       R
>>
>> Insert an element 'C' (at the rear), R <- R+1, X[R] <- 'C'
>>
>>     +---+---+---+---+---
>>     |   | A | B | C |
>>     +---+---+---+---+---
>>       0   1   2   3   4
>>       F           R
>>
>> Remove the front node (the 'A'),
>> F <- F + 1, Y <-- X[F]; if F = R, then set F <-- R <-- 0.
>>
>>     +---+---+---+---+---
>>     |   |   | B | C |
>>     +---+---+---+---+---
>>       0   1   2   3   4
>>           F       R
>
> in base to what you write of above example
> the queue would be afther
> "Remove the front node (the 'A'),"
>
>
>     +---+---+---+---+---
>     |   | A | B | C |
>     +---+---+---+---+---
>       0   1   2   3   4
>           F       R

then there is not the code for check if queue is full [for pushr pushf]
or void [for popr or popf]

[toc] | [prev] | [next] | [standalone]

#913

On 10/10/2011 7:38 AM, arnuld wrote:
...
> I did not understand that how you can say F = F + 1 when you remove an
> item/node/element from the sequential allocation (e.g. array in C ?). The
> front always points to front and rear always points to rear, the values
> inside them may change but front is always a front e.g. if X is a C array
> then:
>
>   X[0]  is always front, no matter what value it has, same for rear. How
> can you say X[1] is front ?
>
> Can someone please explain ?

Remember there are two data structures in play, a logical queue and a
physical array X that is being used, along with F and R, to represent
the FIFO.

X[0] is always the first element of the array, but how the queue
contents are mapped to elements of X is a matter of data structure and
algorithm design. There is nothing forcing X[0] to always contain the
queue head, and the queue can be implemented much more efficiently if
you don't maintain that invariant.

I suggest marking out a small array X on a piece of paper. Also track
the changing values of F and R. Now try pushing a couple of elements
into the queue and popping one, following Knuth's instructions carefully.

Patricia

[toc] | [prev] | [next] | [standalone]

#929

> On Mon, 10 Oct 2011 09:58:16 -0700, Patricia Shanahan wrote:


> Remember there are two data structures in play, a logical queue and a
> physical array X that is being used, along with F and R, to represent
> the FIFO.


Okay, got that.

 
> X[0] is always the first element of the array, but how the queue
> contents are mapped to elements of X is a matter of data structure and
> algorithm design. There is nothing forcing X[0] to always contain the
> queue head, and the queue can be implemented much more efficiently if
> you don't maintain that invariant.
> 
> I suggest marking out a small array X on a piece of paper. Also track
> the changing values of F and R. Now try pushing a couple of elements
> into the queue and popping one, following Knuth's instructions
> carefully.

trust me, I really tried this 4-5 times. The only thing I understood is 
Logical Array can be represented only by numbers like F = 0, R = 3 etc., 
physically it does not exist. Physical Data-Stricture is Array. I really 
wonder if it is necessary to understand the logical Queue when one can 
implement it directly using an Array (in C language e.g.) 




-- 
 arnuld
http://LispMachine.Wordpress.com

[toc] | [prev] | [next] | [standalone]

#928

On Oct 11, 1:38 am, arnuld <sunr...@invalid.address> wrote:

> I did not understand that how you can say F = F + 1 when you remove an
> item/node/element from the sequential allocation (e.g. array in C ?). The
> front always points to front and rear always points to rear, the values
> inside them may change but front is always a front e.g. if X is a C array
> then:
>
>  X[0]  is always front, no matter what value it has, same for rear. How
> can you say X[1] is front ?

When an element is deleted from the front,
it is achieved by incrementing F.
Thus, F[1] becomes the front, and F[0] is effectively deleted.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web