[Jprogramming] special coding for stack operations

[Roger Hui]

You can not win.  The 
   name=: i A. name
in O(1) space and O(1) time requires severe
restrictions on i .  It is easy see that
   name=: x,name
requires O(n) time if there is no extra space
at the front of "name".



----- Original Message -----
From: Dan Bron <jf at dbron.net>
Date: Thursday, July 13, 2006 12:52 pm
Subject: Re: [Jprogramming] special coding for stack operations

> Roger wrote:
> > The bar is higher for prepend/append in-place.
> 
> OK, but since
> 
>           name=: x,name
> 
> is logically equivalent to:
> 
>           name=: name,x          O(1) space, O(1) time
>           name=: i A. name       O(1) space, O(1) time
> 
> for some  i  , then all that remains is to discover a function  
> foo  such that:
> 
> 
>           name ((A.~ foo) -: (|.~ >:)) #x
> 
> and we can have prepend-in-place in  O(1) space, O(1) time.  My 
> brief investigations have led to no obvious definition of  foo  .  
> 
> Here's a table of the first few required outputs of  foo  , where 
> the horizontal axis is  (#name)  and the vertical is  (#x)  :
> 
>           A.@:(|. i.)"0 table~  i. 10
> 	+-------------+-----------------------------------+
> 	|A.@:(|. i.)"0|0 1 2 3  4  5   6    7     8      9|
> 	+-------------+-----------------------------------+
> 	|0            |0 0 0 0  0  0   0    0     0      0|
> 	|1            |0 0 1 3  9 33 153  873  5913  46233|
> 	|2            |0 0 0 4 16 64 304 1744 11824  92464|
> 	|3            |0 0 1 0 18 90 450 2610 17730 138690|
> 	|4            |0 0 0 3  0 96 576 3456 23616 184896|
> 	|5            |0 0 1 4  9  0 600 4200 29400 231000|
> 	|6            |0 0 0 0 16 33   0 4320 34560 276480|
> 	|7            |0 0 1 3 18 64 153    0 35280 317520|
> 	|8            |0 0 0 4  0 90 304  873     0 322560|
> 	|9            |0 0 1 0  9 96 450 1744  5913      0|
> 	+-------------+-----------------------------------+