Linked lists (was osascript - path to me)
Linked lists (was osascript - path to me)
- Subject: Linked lists (was osascript - path to me)
- From: Bill Cheeseman <email@hidden>
- Date: Mon, 20 May 2002 09:14:57 -0400
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?)
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.
To inform and fuel the debate, I append these excerpts from the "General
Notes" file in the AppleScript 1.1 SDK (did you know that Scriptable Text
Editor documents can be opened in TextEdit!?!):
"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, and correspondingly, the characteristics
of these values has changed with respect to efficiency. Efficiency involves
both the amount of time it takes to perform certain operations, and the
amount of space these values consume. Additionally, certain operations can
generate intermediate values (garbage) that are automatically reclaimed by
AppleScript. The more of these intermediate values, the more often the
time-consuming operation of collecting them must occur.
"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. On the positive side, linked lists didn't take up much memory, and
concatenating new item (at least on the left-hand side) was relatively fast
and didn't create any garbage:
"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.
"In AppleScript 1.1, lists are represented as vectors. This means that
elements are stored in consecutive locations in memory rather than linked
together. This makes accessing elements by index fast (constant time -- it
doesn't matter about the value of the index), but makes concatenation
generate much more garbage, as both halves of the concatenate operator (&)
must be copied.
"This trade-off was made because we found that people accessed items of
lists far more often than they concatenated, or more precisely, that this
balance lead to better overall performance characteristics. However, for
certain scripts, the previous list representation may have been more
appropriate, therefore we did two things: We allow linked lists to be
explicitly created, and we allow insertion operations on vectors."
--
Bill Cheeseman - email@hidden
Quechee Software, Quechee, Vermont, USA
http://www.quecheesoftware.com
The AppleScript Sourcebook -
http://www.AppleScriptSourcebook.com
Vermont Recipes -
http://www.stepwise.com/Articles/VermontRecipes
Croquet Club of Vermont -
http://members.valley.net/croquetvermont
_______________________________________________
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.