copying an array...
David Bakhash
adjustable. suppose also that it doesn't have a fill pointer, etc.
Say I want to create an array which is a copy of my-array, but such
that it has a fill-pointer, is adjustable, etc. Also, I don't care
about the original array (i.e. the method can be destructive).
What's the most efficient portable way to do this?
Right now, I am doing:
(setq b (make-array (length my-array)
:displaced-to my-array
:fill-pointer t
:adjustable t))
dave
Steve Gonedes
David Bakhash <ca...@bu.edu> writes:
If you wanted a seperate copy of the array you could use replace. I
think replace is very similiar to memcpy in C; it even takes care of
overlapping correctly when both items to be replaced are eq.
(defun copy-vec (x)
(let ((new-vector (make-array (length x)
:fill-pointer (length x)
:adjustable t)))
(replace new-vector x) new-vector))
Erik Naggum
| What's the most efficient portable way to do this?
use ADJUST-ARRAY.
#:Erik
--
det kommende IT-senteret på Fornebu mangler egentlig bare en flyplass
David Bakhash
> * David Bakhash <ca...@bu.edu>
> | What's the most efficient portable way to do this?
>
> use ADJUST-ARRAY.
As I'd said, the original array was NOT adjustable.
I think that what I posted was actually optimal.
dave
Paul Dietz
> > | What's the most efficient portable way to do this?
> >
> > use ADJUST-ARRAY.
>
> As I'd said, the original array was NOT adjustable.
You can call ADJUST-ARRAY on non-adjustable arrays.
USER(1): (adjust-array "abc" '(10) :initial-element #\b)
"abcbbbbbbb"
USER(2): (adjustable-array-p "abc")
NIL
USER(3): (setq x "abcd")
"abcd"
USER(4): (setq y (adjust-array "abcd" '(4)))
"abcd"
USER(5): (eq x y)
NIL
USER(6): (string= x y)
T
USER(7):
This doesn't copy the array if the initial array *is*
adjustable, though.
Paul
Erik Naggum
| As I'd said, the original array was NOT adjustable.
and as I told you, use ADJUST-ARRAY. read the spec, and be enlightened.
David Bakhash
un-intuitive to me, so I'd never bothered to check that point. But I
noticed that it's non-destructive when you use it on non-adjustable
arrays, which is somewhat weird. I guess that since it's not an error
to use `adjust-array' on non-adjustable arrays, it's probably more
efficient than what I did (e.g. a simple `displaced-to' in a
`make-array').
However, using adjust-array to copy destructively a non-adjustable
array opens up the question of whether to use `displaced-to' in the
`adjust-array' form:
example: want to copy array-1, but make it adjustable, give it a
fill-pointer, etc.
(setq array-2 (adjust-array array-1 (array-dimensions array-1)
:fill-pointer t
:adjustable t))
or
(setq array-2 (adjust-array array-1 (array-dimensions array-1)
:fill-pointer t
:adjustable t
:displaced-to array-1))
This is highly uncertain to me. I'll guess that the latter one is
more efficient, as it won't try to copy data over, which is what I was
afraid of in the first place.
dave
Kent M Pitman
> Yeah. adjust-array works for non-adjustable arrays. It was
> un-intuitive to me, so I'd never bothered to check that point. But I
> noticed that it's non-destructive when you use it on non-adjustable
> arrays, which is somewhat weird.
Think of it like DELETE. It's permitted to adjust the array,
but may not always be able to and so is not (i.e., no longer) required
to. We used to require it to work by side-effect, but that just
led to needless program bugs. (So we traded them for another set of
program bugs which we allege are not needless. :-) You're supposed to do
(setq x (adjust-array x ...))
and are NOT supposed to just assume it reliably works by side-effect.
David Bakhash
> David Bakhash <ca...@bu.edu> writes:
>
> > Yeah. adjust-array works for non-adjustable arrays. It was
> > un-intuitive to me, so I'd never bothered to check that point. But I
> > noticed that it's non-destructive when you use it on non-adjustable
> > arrays, which is somewhat weird.
>
> to. We used to require it to work by side-effect, but that just
> led to needless program bugs. (So we traded them for another set of
> program bugs which we allege are not needless. :-) You're supposed to do
> (setq x (adjust-array x ...))
> and are NOT supposed to just assume it reliably works by side-effect.
that's really a shame. Some fns really should work by side-effect, and
that's one of them. But, in dealing with large strings which are by
default not adjustable, w/ fill-pointers, if I want to "adjust" them to
have these new properties, I really want a way which doesn't try to copy
a string with (potentially) a number of elts in the many hundred to
thousand(s).
So, at the end of the day, I went with:
(setq a (adjust-array a (array-dimensions a)
:fill-pointer t
:adjustable t
:displaced-to a))
I suppose that the above not only is guaranteed to work safely, it
should be as efficient as possible. I just didn't understand why this
is any different from using `make-array' with `:displaced-to' set to the
original one. They seem identical, and thus confusing -- esp. when it's
critical that things be done efficintly.
dave
Kent M Pitman
> Kent M Pitman <pit...@world.std.com> writes:
>
> > David Bakhash <ca...@bu.edu> writes:
> >
> > We used to require it to work by side-effect, but that just
> > led to needless program bugs. (So we traded them for another set of
> > program bugs which we allege are not needless. :-) You're supposed to do
> > (setq x (adjust-array x ...))
> > and are NOT supposed to just assume it reliably works by side-effect.
>
> that's really a shame. Some fns really should work by side-effect, and
> that's one of them.
I think if you think about it, you'll realize this point of view is
selfish. It's much easier for you to do
(defun davids-adjust-array (array &rest options-for-the-elite)
(if (not (adjustable-array-p array))
(error "I'm not going to let you do this except by side-effect~
~%even though I could provide you some help here.")
(apply #'adjust-array options-for-the-elite)))
than it is for someone who has an application that can tolerate the
other form to write something that would extend ADJUST-ARRAY. The solution
we chose makes a number of (though not all) limitations of adjust-array
go away with the addition of a simple SETQ. Your reaction is natural
because you perhaps perceive that an incompatible change was made to
accomodate this class of users; however, your program would have signaled
an error in this case anyway, and the change was not to the "normal"
situation for ADJUST-ARRAY but to the "exceptional" part. That seems a
good trade to me. It still works RELIABLY by side-effect if it is able
(i.e., if you have planned for it by using :ADJUSTABLE T).
> But, in dealing with large strings which are by
> default not adjustable, w/ fill-pointers, if I want to "adjust" them to
> have these new properties, I really want a way which doesn't try to copy
> a string with (potentially) a number of elts in the many hundred to
> thousand(s).
The problem is that you are pointing to a fixed block of storage in most
implementations and trying to in-place extend it. e.g.
+--------------------------------+
| header | cell1 | cell2 | cell3 |
+--------------------------------+
to be
+----------------------------------------+
| header | cell1 | cell2 | cell3 | cell4 |
+----------------------------------------+
The problem is that this would write over the storage cell next to the
array. An adjustable array uses wholly different storage in most
implementations, usually of the form:
+-----------------------------+
| header | pointer to storage |
+-----------------------------+
In this case, you can adjust the array by just doing a conceptual rplacd
of the storage. BUT NOTE: The implementation may still have to allocate
a new storage block and copy the stuff behind your back. So the identity
and side-effect thing is really a red herring. All adjustability is
buying you is that the header to which you point doesn't lose its identity
in the process. The pointer to storage may still look just like the
original array and may still be unable to stretch and you'll be no
better off.
Nothing substitutes for advance planning. That's a property of the
universe, not of Lisp. The problem is that arrays are by their nature
positional, and the nature of positional things is that they may be
positioned next to other things who care about their positions, too.
You can only push so far...
> So, at the end of the day, I went with:
>
> (setq a (adjust-array a (array-dimensions a)
> :fill-pointer t
> :adjustable t
> :displaced-to a))
>
> I suppose that the above not only is guaranteed to work safely, it
> should be as efficient as possible.
You're going to lose here if a is adjustable to begin with. You'll
have made it point to itself. Think about what happens the second
time through.
Also, even if you remove the :DISPLACED-TO, you may not win for the
reasons I've cited above.
Personally, I think if you have the one and only one unique pointer
to the array such that you can do the setq and it will really update all
people who point to it, you're better off with a non-adjustable array
and manual replacement of the array by copy-seq or something simpler.
It will save you the memory indirect on the access. Both :adjustable
and :displaced-to risk some speed on every access due to memory indirect
and should not be done unless you need the functionality (e.g., you're
communicating with modules who don't understand your storage convention
and just want to use a common array abstraction).
> I just didn't understand why this
> is any different from using `make-array' with `:displaced-to' set to the
> original one. They seem identical, and thus confusing -- esp. when it's
> critical that things be done efficintly.
:displaced-to enables sharing and can be cascaded to multiple levels of
indirection. adjust-array is a limited form of the same which may buy
some speed advantages for same. (I think in a system like the lisp
machine with hardware gc pointer forwarding you can get better performance
for adjustable arrays than the worst-case portable performance I described
above; my recollection is that all arrays on the lispm--or nearly all--are
adjustable... hence the funny verbiage about expressly adjustable and
so on in the glossary; extra complication to abstract away from the
specific properties of specific systems.)
Arrays are terribly complicated in programming in general. CL will
provide a variety of services for you to hide the complication, but it
doesn't free you from knowing what you are doing--it only frees you from
doing the actual programming when it comes down to the details.
To the extent that any doc I wrote obscures the intent, you have my
apology. Sadly, for all the HyperSpec is legalistically true, this may
be one of those points where the disclaimer up front about it not being
a tutorial document needs to be taken seriously.
David Bakhash
It's obviously too long for a tutorial, but it's a very good extended
man-page/glossary/index. The only part which I know for sure cannot be
used as a tutorial is the CLOS part. Though thorough, there's no
information there about _how_ CLOS programs should look (IMO). But I'm
glad of it. I don't think that belongs in the HyperSpec. It's really
handy, and though I have the back of Gram's Lisp book for simple things,
I often need the HyperSpec to understand the internals better.
(i.e. thanks).
dave
vnik...@poboxes.com
David Bakhash <ca...@mit.edu> wrote:
(...)
> (setq a (adjust-array a (array-dimensions a)
> :fill-pointer t
> :adjustable t
> :displaced-to a))
>
> I suppose that the above not only is guaranteed to work safely, it
> is any different from using `make-array' with `:displaced-to' set to the
> original one. They seem identical, and thus confusing -- esp. when it's
> critical that things be done efficintly.
MAKE-ARRAY always creates a new array object (i.e. one that is
not EQ to anything else); ADJUST-ARRAY may or may not create a
new object.
More importantly, how legal is it to have an array displaced to
itself? (This must be one of my stupid evenings but I was not
able to figure it out by myself.)
--
Vassil Nikolov
http://www.poboxes.com/vnikolov
-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
vnik...@poboxes.com
My 2e-2:
I would say that literature about Lisp comes in three layers
(Gallia omnia...):
* books that teach Lisp (Winston & Horn, Norvig, whatever);
* books that explain Lisp (CLtL);
* books that define Lisp (HyperSpec).
And one ought to read literature from all three. Then
one may become enlightened (being hit on the head with a
thick InterLisp manual also helps I guess...).
Barry Margolin
>More importantly, how legal is it to have an array displaced to
>itself? (This must be one of my stupid evenings but I was not
>able to figure it out by myself.)
What could this possibly mean? A displaced array doesn't have any storage,
it's simply an alias for another array. AREF has to follow the
displacement links and find real storage cells eventually.
--
Barry Margolin, bar...@bbnplanet.com
GTE Internetworking, Powered by BBN, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Don't bother cc'ing followups to me.
vnik...@poboxes.com
Barry Margolin <bar...@bbnplanet.com> wrote:
> In article <76e2ku$a1d$1...@nnrp1.dejanews.com>, <vnik...@poboxes.com> wrote:
> >More importantly, how legal is it to have an array displaced to
> >itself? (This must be one of my stupid evenings but I was not
> >able to figure it out by myself.)
>
> What could this possibly mean? A displaced array doesn't have any storage,
> it's simply an alias for another array. AREF has to follow the
> displacement links and find real storage cells eventually.
That's what I am asking, since this example was posted recently:
(setq a (adjust-array a (array-dimensions a)
;; ^ ^
:fill-pointer t
:adjustable t
:displaced-to a))
;; ^
Doesn't look right to me but I am not sure I am not missing anything.
vnik...@poboxes.com
Kent M Pitman
> > What could this possibly mean? A displaced array doesn't have any storage,
> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
> > it's simply an alias for another array. AREF has to follow the
> > displacement links and find real storage cells eventually.
I think what you meant was that if it wants to find real storage cells
eventually, it needs to not be a circular arrangement. ;-)
> That's what I am asking, since this example was posted recently:
>
> (setq a (adjust-array a (array-dimensions a)
> ;; ^ ^
> :fill-pointer t
> :adjustable t
> :displaced-to a))
> ;; ^
>
> Doesn't look right to me but I am not sure I am not missing anything.
Didn't look right to me either. Not sure it's illegal.
But neither are circular lists and they're sometimes troublesome,
too. Not every thing that's wrong to do is invalid in the spec;
the same is true of life, btw.
In case you wondered if this was supposed to optimize out into a
displacement to a's old underlying storage, there's no promise to that
effect. Moreover, it wouldn't always be possible, which is why the
array is being adjusted in the first place in many (perhaps most)
cases--the underlying array is too small and needs to be discarded for
a larger one. AND FINALLY, implementations are expressly forbidden
from collapsing "unnecessary" levels of indirection in displaced
arrays--that is, even if an implementation wanted to do something
clever here (though I can't imagine anything that is both clever and
unambiguously right), it would be forbidden to.