The bar is higher for prepend/append in-place.
name=: name,x O(1) space, O(1) time
name=: x,name not in place
name=: x i}name O(1) space, O(1) time
name=: i A. name O(1) space, O(1) time
name=: (<i,j) C. name O(1) space, O(1) time
name=: p{name O(1) space, O(n) time
O(1) really should be O(size of item).
----- Original Message -----
From: Dan Bron <[EMAIL PROTECTED]>
Date: Thursday, July 13, 2006 12:22 pm
Subject: Re: [Jprogramming] special coding for stack operations
> >Hmm, doing name=: p{name in O(1) space and O(n) time
>
> Since you can do name=:name,new_data in O(1) space it is
> possible to do name =: new_data , name in O(1) space and O(n)
> time.
>
> The idea is to "shift in" the new data. That is, append the data
> using the optimized appending code, then rotate the array by
> >:#new_data .
>
> name =: 'abcd'
> name =: name , '123' NB. O(1)
> name =: 4 |. name NB. 4 -: >: # '123'
> name
> 123abcd
>
> I don't know how this scheme compares to the current
> implementation. I suspect that's a question which must be
> answered empirically.
>
> If the scheme is superior, I suggest special casing each of:
>
> name =: name , new_data
> name =: name ,~ new_data
>
> name =: new_data , name
> name =: new_data ,~ name
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
