Re: Linked lists (was osascript - path to me)
Re: Linked lists (was osascript - path to me)
- Subject: Re: Linked lists (was osascript - path to me)
- From: Arthur J Knapp <email@hidden>
- Date: Mon, 20 May 2002 11:30:34 -0400
>
Date: Mon, 20 May 2002 09:14:57 -0400
>
Subject: Linked lists (was osascript - path to me)
>
From: Bill Cheeseman <email@hidden>
>
on 02-05-20 7:55 AM, Christopher Nebel at email@hidden wrote:
>
>
> As for linked lists, they're already there. (I had
>
> been considering removing them. Do you really want them? Why?)
In the context of the previous post, when you said that "they're
already there", did you mean that there was already a "bug" report on
them, or were you referring to the "bracket" linked lists from AS 1.0?
>
Given the lengths to which many people on this list will go to find the most
>
efficient way to script any given task, why would you want to remove an
>
existing technique that can be more efficient (in some senses for some
>
purposes in some circumstances)? If another algorithm that is better on all
>
important points is incorporated into AppleScript, or if keeping linked
>
lists involves a disproportionate development or maintenance cost, then
>
removing linked lists makes sense. Otherwise, I would place the burden of
>
persuasion on those who want to remove something that currently exists. I'm
>
sure linked lists aren't used very often, but that may be only because they
>
aren't currently documented in the ASLG.
When I first discovered that there were linked lists in AppleScript, I
performed extensive tests on them, trying to find if there were any
situations in which they were faster than the "normal" vectors of the
language. I was not able to come up with any situation in which this
was true. The problem with these "linked lists" is that they are only
"linked" behind the scenes, the scripter has no control over the "nodes"
and "pointers". This means that their potential usefulness is primarily
of concern to the AppleScript development team, and not to scripters. As
I said before, if they were to add these kinds of native commands to the
language:
delete (index) from (list)
and it is faster than the 5 to 15-line vanilla handlers that we typically
have to use for deletion, insertion, etc, then what AppleScript is using
behind the scenes is not really that important from the scripter's point
of view. Anything done at the C/C++/Pascal level is going to be "fast
enough" compared to what we can manage at the AppleScript level.
>
To inform and fuel the debate, I append these excerpts from the "General
>
Notes" file in the AppleScript 1.1 SDK
>
"The Story of Lists
>
>
"Representation and Efficiency
>
>
"The way in which lists are represented in memory has changed from
>
AppleScript 1.0 to AppleScript 1.1
>
"In AppleScript 1.0, lists were represented as linked lists in memory.
>
Linked lists means that each item was linked to the next via an internal
>
pointer. ...
>
... linked lists didn't take up much memory,
As opposed to the consecutive memory locations of arrays??? I don't
really understand that.
>
... and
>
concatenating new item (at least on the left-hand side) was relatively fast
>
and didn't create any garbage:
Of course, no one ever likes to have to append to the left-hand side of
a list. It means that collecting items becomes non-intuative, moving from
right to left thru data:
set linkedList to []
set linkedList to [last item] & linkedList
set linkedList to [second to last item] & linkedList
etc...
Besides, my tests always showed that vector appending was faster:
set beginning of myVectorList to myValue
set end of myVectorList to myValue
>
"On the negative side, linked lists took longer to reach elements at higher
>
indicies than they did to reach elements at lower indicies (i.e. the access
>
time was linear (increased proportionally) to the index of the item being
>
accessed). This is because the list had to be traversed from beginning,
>
counting up to the index of the item desired. Also, if you were unfortunate
>
enough to concatenate on the right-hand side, the entire left-hand side of
>
the list would have to be copied. This is because we mustn't change the
>
left-hand side value to perminantly [sic] be concatenated with the
>
right-hand side because other parts of the program may still be using its
>
old value.
Why was AppleScript designed to do everything via concatenation? It is a
language that just loves to move large pieces of data around for no
appearent reason. ;-)
P.S. How cool that I was somehow able to drag both Chris Nebel and Bill
Cheeseman into the same thread. ;-)
{ Arthur J. Knapp, of <
http://www.STELLARViSIONs.com>
<
mailto:email@hidden>
try
<
http://members.bellatlantic.net/~bswaldie/>
on error number -128
end try
}
_______________________________________________
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.