[Wanted]: Best and fastest way to mix a list's items randomly

This is what I use for mixing a list right now:

mixList({"a", "b", "c", "d", "e"})

on mixList(foo)
	--This "repeat" will create a list with new locations for each single list item
	--If you have a very long list or very memory-intensive (very large unicode texts for example) items it might slow down the mixing a lot - so I build up a temporary list called "bar".
	--This code only compares the indexes if they already exist - not the list items' contents which might be pretty heavy stuff!
	set bar to {}
	repeat
		if (count bar) < (count foo) then
			set therandom to (random number from 1 to (count foo))
			if bar does not contain therandom then set end of bar to therandom
		else
			exit repeat
		end if
	end repeat
	bar
	--Now I take the new locations out of "bar" and use them to reorder the items of list "foo" in a new list called foobar
	set foobar to {}
	repeat with i from 1 to (count foo)
		set end of foobar to item (item i of bar) of foo
	end repeat
	return foobar
end mixList


--This handler takes 2.5 milliseconds for a list of 5 items
--but takes 252.0 milliseconds for a list of 100 items
--So this handler works fine for small lists but just sux0rs for lists with 10+ items

The leak is here:

set therandom to (random number from 1 to (count foo))
if bar does not contain therandom then set end of bar to therandom

How do I best tell the handler to exclude already set indexes from the random number range as this is where it leaks?

Couldn’t find a solution for this.:mad:

Hi, Vincent.

This is quite good:

on mixList(theList)
	script o
		property l : theList
	end script
	
	set limit to (count theList) - 1
	repeat with i from 1 to limit + 1
		set j to (random number limit) + 1
		tell item i of o's l
			set item i of o's l to item j of o's l
			set item j of o's l to it
		end tell
	end repeat
end mixList

It sorts the actual list presented to it, so if you call it with ‘mixList(myList)’, then it’s myList that’ll end up being sorted, not a copy. Other speed bumps come from the script object, which enables the list to be accessed via a reference (giving faster access to its items), and the single-parameter use of random number, which is faster than using the from and to parameters. The single random number parameter returns a number between 0 and the number you supply, so here we ask for a random number between 0 and (list length - 1) and add 1 to the result. Even faster results can be obtained if you write your own AppleScript-language random number generator, which will probably be faster than the OSAX call.

Finally, of course, the handler exchanges each item in the list with another item from the same list, chosen at random. It doesn’t matter if a particular value’s exchanged more than once, only that it’s not duplicated in the final result. This saves having to check whether or not the value’s already been “done”.

Hi Nigel,

thanx a lot! Works great and lightning fast! And your solution is so damn simple and brilliant.

Ahem, just curious . how would such a vanilla handler look like?:rolleyes:
I mean, how do you build a random number generator in AS without using the OSAX’s “random number” term?

Expanding on Nigel’s, give this script a try, Vincent:

on mixList(theList)
	script o
		property l : theList
		property c : {1}
	end script
	
	set limit to count of theList
	if limit is 1 then return theList
	
	repeat with i from 2 to limit
		set end of o's c to i
		set j to some item of o's c
		tell item i of o's l
			set item i of o's l to item j of o's l
			set item j of o's l to it
		end tell
	end repeat
	return theList
end mixList

mixList({"a", "b", "c", "d", "e"})

Which leads to the fun experiment: ‘How many times will the list return to it’s origin if you keep randomizing it?’ Answer - in 10,000 tries, the answer is usually between 70 and 90. On my dual-core G5, this only takes a bit over a second, so if you’re running a slower machine, you might want to change the number of trials.

[Note: I think it’s safe to say that in this forum and others, Nigel Garvey is the master of speed (among other things) and Kai is the master of brevity (among other things) for AppleScript - a standing that results from a deep understanding of the inner works of AppleScript probably only rivaled by Chris Nebel; the AppleScript guru at Apple.]


on mixList(theList)
	script o
		property l : theList
		property c : {1}
	end script
	
	set limit to count of theList
	if limit is 1 then return theList
	
	repeat with i from 2 to limit
		set end of o's c to i
		set j to some item of o's c
		tell item i of o's l
			set item i of o's l to item j of o's l
			set item j of o's l to it
		end tell
	end repeat
	return theList
end mixList

script l
	property M : {}
	property T : {"a", "b", "c", "d", "e"}
end script
set l's M to {} -- otherwise the results are cumulative
repeat with k from 1 to 10000
	set l's T to mixList(l's T)
	if l's T = {"a", "b", "c", "d", "e"} then set end of l's M to k
end repeat
set R to count l's M

Ha! I’ve been trying to work out why Qwerty posted a script that’s plainly much slower than the one I posted earlier. It turns out that it’s only slower with lists of more than about 23000 items. (I was testing with 40000!) Below that, Qwerty’s version easily outruns mine on my machine. Below about 5000 items, it’s even faster than a version I’ve been trying with a (not wonderfully random) random number generator I wrote three years ago, so it should be good enough for most purposes. Nice one, Q! :cool:

Or simply make a probability-based estimate:


to get_factorial for l
	set f to 1
	repeat with i from 2 to count l
		set f to f * i
	end repeat
	f
end get_factorial

set test_list to {"a", "b", "c", "d", "e"}
set total_tries to 10000
total_tries div (get_factorial for test_list)

--> 83

:wink:

Yeah but I only took about 20 Maths courses on the way to a doctorate in Mechanical Engineering - and, I didn’t even think of computing it. :rolleyes: Can you tell I was an experimentalist rather than theoretician? 10,000 div (5!), given that order is important. duh.