Re: Appending a list to a list and getting one list.
Re: Appending a list to a list and getting one list.
- Subject: Re: Appending a list to a list and getting one list.
- From: Christopher Nebel <email@hidden>
- Date: Mon, 20 May 2002 04:41:01 -0700
On Tuesday, May 14, 2002, at 05:03 AM, has wrote:
OK, in truth I don't really know how AS actually performs these two
operations internally. Perhaps there's some lookahead in the compiler
that's smart enough to say "I'm going to make sure this list has extra
memory space allocated to it so I've got some room to append extra
items to
it without having to move home so often." Or maybe the list is able to
grow
into any adjoining free memory during appends? Or perhaps AS adds a
pointer
to the end of the existing memory block that points to a second block
where
the list continues?
You asked for it!
Say you've got a list of n items and a list of m items, and you want to
tack the two together.
Concatenation allocates an entirely new list of size n+m and copies the
two original lists into it, so it does O(n+m) work.
Setting the end (appending) grows the storage in chunks of 16 items,
leaving a little empty space at the end. Therefore, if m is
sufficiently small (e.g., 1), it might take only O(m) time. However, if
m is larger than the empty space available, the first list will have to
be reallocated, which means you're doing O(n+m) work again. Appending
items one at a time is not very efficient, because every 16 items, it'll
have to reallocate, so for n items you wind up with O(n^2) work.
However, it's still a better deal than concatenation, which reallocates
every time, so it's about 16 times slower.
Before anyone says anything, yes, I know about different reallocation
strategies that would could add an item in amortized constant time
instead of linear. All of this only applies for existing versions of
AppleScript, of course.
--Chris Nebel
AppleScript Engineering
_______________________________________________
applescript-users mailing list | email@hidden
Help/Unsubscribe/Archives:
http://www.lists.apple.com/mailman/listinfo/applescript-users
Do not post admin requests to the list. They will be ignored.