Re: AppleScript lists are O(1) vectors (was Re: AS Library Question)
Re: AppleScript lists are O(1) vectors (was Re: AS Library Question)
- Subject: Re: AppleScript lists are O(1) vectors (was Re: AS Library Question)
- From: has <email@hidden>
- Date: Sat, 09 Jan 2016 21:05:52 +0000
On 22/12/2015 01:53, Chris Page wrote:
On Dec 20, 2015, at 2:13 AM, has <email@hidden> wrote:
Well, if you're going to talk about things on the AS devs can do, I'd very much like to see AppleScript lists with O(1) lookup, like in every other language that uses vector arrays.
AppleScript lists are O(1) vectors. What leads you to believe they aren't?
Uh... Hard Reality, mate:
on testit()
set t to script "TestLib"'s makeTimer()
repeat with n in {1, 10, 100, 1000, 10000}
-- build a list of n items
set L to {0}
repeat while L's length < n
set L to L & L
end repeat
if L's length > n then set L to items 1 thru n of L
-- now look up a list item (1000 times)
t's startTimer()
set midIndex to ((L's length) + 1) div 2
repeat 1000 times
get item midIndex of L
end repeat
-- compare size of list vs lookup time
log {L's length, (t's stopTimer()) * 1000}
end repeat
end testit
testit()
-- Results:
(*1, 0.890016555786*)
(*10, 1.330971717834*)
(*100, 4.957020282745*)
(*1000, 38.338005542755*)
(*10000, 383.955001831055*)
--> time to get/set a list item varies linearly with length of list,
i.e. O(n)
Actually, the vector array part is O(1) as expected, but AS's full
`list` implementation ruins this by slapping some poorly conceived
"safety check" [IIRC] code that degrades its efficiency to O(n). Which
is ironic, given that AS's vector array implementation was introduced in
order to fix the inevitably lousy performance of AS's original O(n)
linked list implementation.
Every seasoned AppleScripter knows about this performance hole - I even
covered it in the Apress book - and many are all too familiar with the
horrible "use a reference to the reference" kludge that somehow manages
to avoid the duff algorithm, giving the expected O(1) efficiency at the
cost of hellish ugly and tricky-to-debug code:
on testit()
set t to script "TestLib"'s makeTimer()
repeat with n in {1, 10, 100, 1000, 10000}
-- build a list of n items, this time wrapping in a script
object property so we can look up items using a reference
script K
property L : {0}
end script
repeat while K's L's length < n
set K's L to K's L & K's L
end repeat
if K's L's length > n then set K's L to items 1 thru n of K's L
-- now look up a list item (1000 times)
t's startTimer()
set midIndex to ((K's L's length) + 1) div 2
repeat 1000 times
get item midIndex of K's L
end repeat
-- compare size of list vs lookup time
log {K's L's length, (t's stopTimer()) * 1000}
end repeat
end testit
testit()
-- Results:
(*1, 1.091003417969*)
(*10, 0.979006290436*)
(*100, 0.958025455475*)
(*1000, 1.241028308868*)
(*10000, 1.428008079529*)
--> time to get/set a list item is constant, i.e. O(1), regardless of
length of list
Regards,
has
p.s. Actually, I briefly thought it'd been fixed in 10.11, but not so: I
just screwed up my timing tests. Too much Xmas cheer on my part, no
doubt. So back to das kludgercoden I go.
p.p.s. For extra amusement, AS still supports its original `linked list`
type, which uses square brackets instead of curly braces for its literal
form, so you can compare the performance profiles by changing `{0}` to
`[0]` in the above scripts.
_______________________________________________
Do not post admin requests to the list. They will be ignored.
AppleScript-Users mailing list (email@hidden)
Help/Unsubscribe/Update your Subscription:
Archives: http://lists.apple.com/archives/applescript-users
This email sent to email@hidden