« Joel's got it right; it's about browser-share, not designers | Main | Demo now available for Webmail »

Fast, random sorting of queries, arrays, lists, and structs

I need to create a page that takes a structure of members and displays it in random order on the page (kind of an ever-changing "here are the latest members to sign up on our site" table). I needed to work with a struct because 1) it's what our CFC was built to return, and 2) the member data had a nested hierarchy that would have been impossible to output easily if it were in a query. While Googling on randomization, I came across Ben Nadel's post yesterday on randomly-ordered lists. He makes an interesting comparison between different methods of sorting: by sorting a struct (fast but doesn't allow duplicates), random append/prepend from one list to another (slow), multiple swapping of items in an array (fast, but perhaps not very random), and random selection from one list into another (extremely slow). So it occurred to me that with a bit more thought about the sorting algorithm, I should be able to build on Ben's work to create a randomization function that was speedy, handled duplicates, and could return a random list (or list of keys) when passed a structure, array, query, or list.

The first part of the function was pretty simple to come up with: check what kind of object is passed to the function, and pull the appropriate data out of it to make into a sortable list. For instance, if we're passed a struct, we get a list of its keys; if we're passed an a query, we create a list containing the row numbers; and if we're passed an array, we also get a list of index numbers.

<cffunction name="randomizeList" output="no">
	<cfargument name="object" type="any" required="yes" />
	<cfset var list = '' />
	<cfset var randomPos = 1 />
	<cfset var result = ArrayNew(1) />
	
	<!--- Create a sorted list depending on the type of object passed in --->
	<cfif IsStruct(ARGUMENTS.object)>
		<cfset list = StructKeyList(ARGUMENTS.object)>
	<cfelseif IsQuery(ARGUMENTS.object)>
		<cfloop index="index" from="1" to="#ARGUMENTS.object.recordCount#">
			<cfset list = ListAppend(list, index) />
		</cfloop>
	<cfelseif IsArray(ARGUMENTS.object)>
		<cfloop index="index" from="1" to="#ArrayLen(ARGUMENTS.object)#">
			<cfset list = ListAppend(list, index) />
		</cfloop>
	<cfelse>
		<cfset list = ARGUMENTS.object />
	</cfif>
	
	...

Originally, my idea was to just pluck elements out of that list at random and append them to a new list. This worked, but was really slow when tested against the same 6000-name list that Ben tested against. So I took Ben's advice and converted the list to an array; then plucked items out of the array at random and appended them to a new array; and finally, returned the array to the user as a list. With that resulting list in hand, you can loop through the original struct, query, or array in random order. Here's the final code, which runs in 50-200ms:

<cffunction name="randomizeList" output="no">
	<cfargument name="object" type="any" required="yes" />
	<cfset var list = '' />
	<cfset var randomPos = 1 />
	<cfset var result = ArrayNew(1) />
	
	<!--- Create a sorted list depending on the type of object passed in --->
	<cfif IsStruct(ARGUMENTS.object)>
		<cfset list = StructKeyList(ARGUMENTS.object)>
	<cfelseif IsQuery(ARGUMENTS.object)>
		<cfloop index="index" from="1" to="#ARGUMENTS.object.recordCount#">
			<cfset list = ListAppend(list, index) />
		</cfloop>
	<cfelseif IsArray(ARGUMENTS.object)>
		<cfloop index="index" from="1" to="#ArrayLen(ARGUMENTS.object)#">
			<cfset list = ListAppend(list, index) />
		</cfloop>
	<cfelse>
		<cfset list = ARGUMENTS.object />
	</cfif>
	
	<!--- Convert the list to an array for speed --->
	<cfset list = ListToArray(list) />
	
	<!--- As many times as there are items in the current list --->
	<cfloop index="i" from="1" to="#ArrayLen(list)#">
		<!--- Add one list item at random to the results --->
		<cfset randomPos = RandRange(1, ArrayLen(list)) />
		<cfset ArrayAppend(result, list[randomPos]) />
		<!--- Remove that list item --->
		<cfset ArrayDeleteAt(list, randomPos) />
	</cfloop>

	<cfreturn ArrayToList(result) />
</cffunction>

If you need a randomized list, that's what you get back out. But if you want to show random items from an object such as a struct, just do the following:

<cfloop index="i" list="#RandomizeList(yourStruct)#">
	<cfoutput>#yourStruct[i].name#<br /></cfoutput>
</cfloop>

Comments (6)

@Tom,

Looks good. Glad I could help inspire some solid creativity.

Tom,
Much obliged, found very useful for displaying a structure full of arrays in a random fashion.

Excellent. Thank you for posting. Seems like a simple thing to want to display results in random order, but I, like Ben, couldn't find anything on it either.

Nicely done, this came in very handy for some query manipulation documentation I'm writing up for my work group. I like that you can pass in any type of object as well.

Just found this... thank you!

I found this a few months back and implemented it. I couldn't get it to work though. I just tried it again and it works great. Yeah, you would think CF would have a built in arraySort() function.

Thanks so much to you and Ben Nadel for your help! (I found your link on his blog!)

Post a comment