Randomly Sorting A ColdFusion List
Posted August 25, 2006 at 12:59 PM
The other day, Si asked me if I knew how to randomize a given list. This is something that I figured would be really easy, but was actually a bit stumped. I mean, I could figure it out, but none of the ways seemed very easy or short. I checked out CFLib.org, but couldn't find anything (maybe I didn't know how to search for it). So, I came up with four different methods, each of which has different pros and cons.
For each of the methods below, assume that I have this list:
Launch code in new window » Download code as text file »
- <!--- Set up list of girls. --->
- <cfset lstGirls = RepeatString(
- "molly,sarah,julie,julia,ashley,annie,",
- 1000
- ) />
Notice that I am REPEATING that list via RepeatString() 1000 times. I need to get a very large list so that the speed differences are apparent (6000 items in total).
Method 1: StructSort()
This method leverages the sorting of structures and then the use of their key lists:
Launch code in new window » Download code as text file »
- <!--- Set the struct holder. --->
- <cfset objRandomGirls = StructNew() />
-
- <!--- Loop over the list of girls. --->
- <cfloop index="strGirl" list="#lstGirls#" delimiters=",">
-
- <!--- Add the girls to the struct as the key with a random value. --->
- <cfset objRandomGirls[ strGirl ] = RandRange( 1111, 9999 ) />
-
- </cfloop>
-
- <!--- Get the random list. --->
- <cfset lstRandomGirls = ArrayToList(
- StructSort( objRandomGirls, "numeric", "ASC" )
- ) />
As you can see in this one, each girl is a key in struct. For each girl, I assign a random number, then sort the struct on that number. The resultant array is then converted back into a list. This runs very fast, at about 50ms for 6000 girls. The problem that you very quickly see though, is that it does NOT allow for duplicates. Each repeated girl name is stored at the SAME key in the struct and so, the resultant, random list is only 6 girls long. So fast, but NOT useful (except if maybe you have no repeating values).
Method 2: ListAppend() / ListPrepend()
For this method, I basically take one girl at a time and randomly append or prepend her to the new list.
Launch code in new window » Download code as text file »
- <!--- Set the random list. --->
- <cfset lstRandomGirls = "" />
-
- <!--- Loop over the list of girls. --->
- <cfloop index="strGirl" list="#lstGirls#" delimiters=",">
-
- <!--- Decide if we are appending or prepending. --->
- <cfif RandRange( 0, 1 )>
-
- <!--- Append the girl. --->
- <cfset lstRandomGirls = ListAppend(
- lstRandomGirls,
- strGirl
- ) />
-
- <cfelse>
-
- <!--- Prepend the girl. --->
- <cfset lstRandomGirls = ListPrepend(
- lstRandomGirls,
- strGirl
- ) />
-
- </cfif>
-
- </cfloop>
At the end of this (as always) lstRandomGirls will have the random list. This method is both slow (running at about 2000ms for 6000 girls) and not very useful. The randomization is very limited when you can only add an item to a list in two ways.
Method 3: ArraySwap()
In this method, I tried using an array since array access times are much better than list access times. We convert the list to an array and then randomly swap items.
Launch code in new window » Download code as text file »
- <!--- Set the random array. --->
- <cfset arrGirls = ListToArray( lstGirls ) />
-
- <!--- Get the length of the array. --->
- <cfset intLength = ArrayLen( arrGirls ) />
-
- <!--- Iterate the number of girls x 2. --->
- <cfloop index="intIndex" from="1" to="#(intLength * 2)#" step="1">
-
- <cfset ArraySwap(
- arrGirls,
- RandRange( 1, intLength ),
- RandRange( 1, intLength )
- ) />
-
- </cfloop>
-
- <!--- Get the random list. --->
- <cfset lstRandomGirls = ArrayToList( arrGirls ) />
If you will notice, I randomly swap items a total of (N x 2) times where N is the length of the list. I decided to go x2 times just to increase the random factor. This method is actually fairly fast running in anywhere from 50ms to 230ms per 6000 girls. It actually creates a fairly random list as well, despite the fact that method is not very clever.
Method 4: ListInsertAt()
In this method, I am reading the given list and then randomly inserting it into the randomized list.
Launch code in new window » Download code as text file »
- <!--- Set the random list. --->
- <cfset lstRandomGirls = "" />
-
- <!--- Set the counter. --->
- <cfset intCounter = 0 />
-
- <!--- Loop over the list of girls. --->
- <cfloop index="strGirl" list="#lstGirls#" delimiters=",">
-
- <!--- Check to see which iteration we are on. --->
- <cfif intCounter>
-
- <!--- Insert that girl in a random place. --->
- <cfset lstRandomGirls = ListInsertAt(
- lstRandomGirls,
- RandRange( 1, intCounter ),
- strGirl
- ) />
-
- <cfelse>
-
- <!--- Start the list. --->
- <cfset lstRandomGirls = strGirl />
-
- </cfif>
-
- <!--- Increment the counter. --->
- <cfset intCounter = (intCounter + 1) />
-
- </cfloop>
This method is sooo slow that is started to timeout the page (even when my timeout was 900 seconds) for 6000 girls. Not only is it slow, I hate the fact that ListInsertAt() does NOT work for an empty list - hence the need for an initial setting of the random string.
So there are my four methods, two of which actually might be useful. Right now, I am leaning towards the ArraySort() one as I am picturing a user defined function (UDF) that, as an optional argument, can take the number of swapping iterations to make. However I do it though, I still with there was a simpler, faster answer.
Note: I have totally missed a built in way of doing this, PLEASE let me know :)
Download Code Snippet ZIP File
Post Comment | Ask Ben | Permalink | Other Searches | Print Page
Newer Post
Creating A PING-Like Browser Bookmark For Feed-Squirrel
Older Post
Tim Cracked The GMail - CFMailPart Puzzle!
Reader Comments
Ben, this is a really interesting article. It gave me some good inspiration for a UDF that returns a random list for a query, array, or struct:
http://www.mollerus.net/tom/blog/2008/03/creating_randomlyordered_lists.html
The first way works quite well if your list is really a set not a list. That way your struct will always be the same size as your set.
I use this when presenting a random subset of a query. I use a value list of the primary keys to build the list.
