Speed-enhancing techniques for use with large lists

Scripting Forums AppleScript | Mac OS X
#1

There have been a number of threads of late that dealt with methods which can be used to improve the time it takes to read from and write to large lists. I just finished some additional testing on this topic and, FWIW, thought I would include the results here. I have not copied each script below and instead have included only the code being timed. The names I use for the two script-object methods may not be technically correct but I couldn’t think of anything else.

NO SPEED ENHANCEMENT - 142 seconds

use framework "Foundation"
use scripting additions

-- untimed code
set aList to {"Abraham", "Barbara", "Charles"}
repeat 14 times
	set aList to aList & aList
end repeat
set aList to aList & "Extra"
set aList to aList & {"Abraham", "Barbara", "Charles"}

-- start time
set startTime to current application's CFAbsoluteTimeGetCurrent()

-- timed code
set newList to {}
repeat with i from 1 to (count aList)
	if item i of aList = "Extra" then
		exit repeat
	else
		set end of newList to item i of aList
	end if
end repeat

-- elapsed time
set elapsedTime to (current application's CFAbsoluteTimeGetCurrent()) - startTime
set nf to current application's NSNumberFormatter's new()
nf's setFormat:("0.000")
set elapsedTime to ((nf's stringFromNumber:elapsedTime) as text) & " seconds"

-- result
elapsedTime

A REFERENCE TO - 1.187 seconds

-- timed code
set aListRef to a reference to aList
set newList to {}
set newListRef to a reference to newList
repeat with i from 1 to (count aListRef)
	if item i of aListRef = "Extra" then
		exit repeat
	else
		set end of newListRef to item i of aListRef
	end if
end repeat

EXPLICIT SCRIPT OBJECT - 0.802 seconds

-- timed code
main(aList)
on main(aList)
	script o
		property aListRef : aList
		property newList : {}
	end script
	repeat with i from 1 to (count o's aListRef)
		if item i of o's aListRef = "Extra" then
			exit repeat
		else
			set end of o's newList to item i of o's aListRef
		end if
	end repeat
end main

IMPLICIT SCRIPT OBJECT - 0.777 seconds

-- timed code
set newList to my {}
repeat with i from 1 to (count my aList)
	if item i of my aList = "Extra" then
		exit repeat
	else
		set end of my newList to item i of my aList
	end if
end repeat

A few comments:

  • The basic procedure used to time the scripts was written by Nigel.
  • The code under the comment “elapsed time” was written by Shane.
  • The source and output lists contain 49,156 and 49,152 items.
#2

I am working to better understand AppleScript sort routines and, while doing this, decided to look at the impact on execution time of referencing script objects. To begin, I created a list of numbers from 1 to 1,000 and then randomized these numbers in a second list named theList.

-- untimed code
set maxValue to 1000
set numberList to {}
repeat with i from 1 to maxValue
	set end of numberList to i
end repeat
set theList to {}
repeat maxValue times
	set r to some number of numberList
	set end of theList to r
	set item r of numberList to missing value
end repeat

I then ran a standard bubble sort, which took 26.5 seconds:

-- timed code
repeat with i from (count theList) to 2 by -1
	set a to beginning of theList
	repeat with j from 2 to i
		set b to item j of theList
		if (a > b) then
			set item (j - 1) of theList to b
			set item j of theList to a
		else
			set a to b
		end if
	end repeat
end repeat

Then a speed-enhanced version of the same bubble sort, which took 0.753 seconds:

-- timed code
repeat with i from (count my theList) to 2 by -1
	set a to beginning of my theList
	repeat with j from 2 to i
		set b to item j of my theList
		if (a > b) then
			set item (j - 1) of my theList to b
			set item j of my theList to a
		else
			set a to b
		end if
	end repeat
end repeat

Then a script I wrote, which took 0.363 seconds:

-- timed code
set sortedList to listSort(theList)
on listSort(unsortedList)
	script o
		property u : unsortedList
		property s : {}
	end script
	repeat ((count o's u) - 1) times
		set lowIndex to 1
		set lowItem to item 1 of o's u
		repeat with i from 2 to (count o's u)
			if item i of o's u < lowItem then
				set lowIndex to i
				set lowItem to item i of o's u
			end if
		end repeat
		set end of o's s to lowItem
		set item lowIndex of o's u to missing value
		set o's u to integers of o's u
	end repeat
	return (o's s & o's u)
end listSort

Then two of Nigel’s sort routines in:

https://macscripter.net/viewtopic.php?id=22911

The results were:

Bubble sort in a handler: 0.747 seconds
Squeeze sort: 0.247 seconds

Then, Adam Bell’s implementation of Quick Sort in post 1 of:

https://macscripter.net/viewtopic.php?id=17340

The initial timing result was 0.235 seconds, but this was reduced to 0.027 seconds after making the following change, which more effectively referenced a script object:

tell A's L to set {item i, item j} to {item j, item i} -- the original code
set {item i of A's L, item j of A's L} to {item j of A's L, item i of A's L} -- my modification

Although it has nothing to do with referencing script objects, I tested an ASObjC routine from a post by Shane, which took 0.007 seconds with everything in memory. However, the first-run time from a cold start was in excess of 0.230 seconds,

set theArray to current application's NSArray's arrayWithArray:theList
set sortedList to (theArray's sortedArrayUsingSelector:"compare:") as list

Just as a point of credit, I obtained the script creating the test list from a post by Nigel.

#3

Here is a more efficient routine to generate a random list of numbers


set maxValue to 1000

set theList to {1}

set c to 1
repeat with i from 2 to maxValue
	set end of my theList to item c of my theList
	set item c of my theList to i
	set c to random number from 1 to i
end repeat

Only loops once

Also you can’t use “My” on a list if it is local to a subroutine
you would do something like this:


set maxValue to 1000

set theList to {1}

set c to 1
repeat with i from 2 to maxValue
	set end of my theList to item c of my theList
	set item c of my theList to i
	set c to random number from 1 to i
end repeat

bubbleSort(theList)

on bubbleSort(theList)
	script M
		property alist : theList
	end script
	repeat with i from (count M's alist) to 2 by -1
		set a to beginning of M's alist
		repeat with j from 2 to i
			set b to item j of M's alist
			if (a > b) then
				set item (j - 1) of M's alist to b
				set item j of M's alist to a
			else
				set a to b
			end if
		end repeat
	end repeat
end bubbleSort
#4

Here are a couple of others, that are fractionally more efficient:

use framework "Foundation"
use framework "GameplayKit"
use scripting additions

set x to current application's GKARC4RandomSource's sharedRandom()
set theList to {}
repeat 1000 times
	set end of theList to x's nextIntWithUpperBound:10000
end repeat

And:

use framework "Foundation"
use framework "GameplayKit"
use scripting additions

set x to current application's GKRandomDistribution's distributionWithLowestValue:1 highestValue:1000
set theList to {}
repeat 1000 times
	set end of theList to x's nextInt()
end repeat

Both require 10.11 or later.