Using ColdFusion Structures To Remove Duplicate List Values

Very Clean!

There are other ways to remove duplicates in a list, but none as elegant as this.

Good Show!

Dan Wilson

Thanks! I've been looking for a way to speed up the creation of a unique 5 character id list I create for emails tracking in one of our products. The best way I could find to keep the list unique was just using string contains on a list but your struct alternative is MUCH faster. I'm still checking my code but here are some figures:

2,000 IDs
- List/String = 1797ms
- Struct = 171ms

10,000 IDs
- List/String = 41750ms
- Struct = 937ms

100,000 IDs
- List/String (not going to do it now, tried in the past and its like 20 minutes)
- Struct = 50266ms (WOW!)

I have it flushing counts every 100 ID attempts and it pauses around 36800 and 74900 every time so there is some type of conversion going on around those sizes. I noticed similar pauses occurring when using strings.

The algorithm is close to linear instead of growing in time based on the size of the list. Don't remember all that Big O notation stuff to explain that further.

I'm no regexp ninja but would you not be better just using regular expressions?

nothing at hand at the moment to show for code, but thought i'd chuck that in the ring

Hey Ben,

VERY cool! Very cool indeed!

Now how about an easy way to tell *which* elements of the list are duplicated?

The regular expression idea interests me. I'm curious about the efficiency of checking for duplicates across a list in a single regular expression search. Not as efficient as structs for deduping but if you have to find dupes it may be faster than looping for every item in list.

First you would need to sort the list, then run a regular expression such as the following "(,|$)([^,]+),\2(,|^)".

Just remembered though that REFind only returns the first match so that would require some looping to find the next match. hmmm

I'm not actually advocating a loop through each piece of data, rather an REFind on an entire list string using the delimiter in regular expression to detect dupes. The benefit with a regular expression in this instance over an array loop is that you are only looping as many times as there are matches and you are able to start where you left off.

For example with the regular expression, if there are no duplicates you would do a single REFind which would find no duplicates and you would be done. If it found one you would start another REFind from where you found the first dupe to look for the next.

A loop over each item in the list or array on the other hand would require an action on ever item in the list to compare to every other item in the list. That quickly looses efficiency because processing increases exponentially, which was the need for the struct work around of course.

Anyways, something to think about and I might play with when I have time.

Though the RE method may help us find duplicates be it tell us they exist or tell us which are the duplicates the original purpose of this post was to REMOVE duplicates not to find them.

For it's purpose this works well enough in comparison to the alternatives out there which serve ONLY this purpose and no extra.

As a thought should you find your data in a Query object (say you pulled a list from you database and you only want the unique entries for a particular column where the db does not have this constraint imposed) a QofQ may work and scale far better than this method. Where the method here is linear (O(n)) for those that know the notation it is possible the QoQ method may be < O(n) for larger datasets.

Absolutley love this, have used the technique a few times!

How about a way to count the occurrences of each value in the list, before or during the conversion to a struct key list?

This is a great approach! Thanks for laying out the logic so easily and cleanly. I remember relying on a UDF from cflib.org that also removed duplicates. This one would loop through each list item and add it to a second list only if it hadn't been seen before. As the second list gets larger then searching gets slower. The method shown here would definitely be faster as others have already pointed out. Shoot, Adobe might as well take the code here and make a built-in function out of it. I can dream, can't I?

I wrote this to count the occurrences of each item when looping a populated list with redundancies into a struct. Worked pretty well. Thanks for the original idea!! :-)

<cfloop index="tag" list="#tagList#" delimiters=",">
<cfset tag1 = trim(#tag#)>
<cfif tag1 neq "">
<cfif structKeyExists(tagStruct,"#tag1#")>
<cfset tagStruct[tag1] = #tagStruct[tag1]# + 1>
<cfelse>
<cfset tagStruct[tag1] = "1" />
</cfif>
</cfif>
</cfloop>

Ben,

Great post! Used it on a couple different projects in the past week! Thanks!!

This is something that is making me pull my hair out, and still is.

I would like to order the results based on the number of occurrences, if a result or particular ID shows up more than once it would have a higher position in the array or list. Then the ones that have less would follow behind.

This is really driving me bonkers.

@Jody

To the best of my knowledge, structures don't really have a notion of ordering, so you would have to convert the structure to some other data type such as 2D array or a query.

If you wanted to go the query route, you first convert your structure to a query and then run a query of queries to run your sort.

<!--- convert struct to query --->
<cfscript>
struct = { one = 1, two = 2, three = 3, four = 4, five = 5 };
query = queryNew( "key,num" );
for ( key in struct ){
queryAddRow( query );
querySetCell( query, "key", key );
querySetCell( query, "num", struct[key] );
}
</cfscript>

<!--- query of queries --->
<cfquery name="qSort" dbtype="query">
SELECT *
FROM query
ORDER BY num desc
</cfquery>

<cfdump var="#struct#" />
<cfdump var="#query#" />
<cfdump var="#qSort#" />

I got my inspiration for this workaround from the following tutorials.

http://www.coldfusioncookbook.com/entry/23/How-do-you-loop-over-the-values-in-a-structure?

http://www.coldfusioncookbook.com/entry/87/How-do-I-sort-a-2-dimensional-array?

If you wanted to go the 2D array route, you could use the code from the latter of the two links above.

I don't think that's what Jody was exactly looking for but at least it's close.

If there's an array with duplicates I believe Jody wants them ordered from most to least? Obviously the easiest way is likely:

1. Create the 'unique key' structure defined above with value = 0
2. Loop the array incrementing a counter each time a value is seen
3. Iterate the new structure creating again ANOTHER structure where the keys are the numerical counters stored in struct1. When you have 2 keys with the same counter make the value a list or an array of the appropriate text keys.

You can of course use a QofQ method:

<cfscript>
array = ListToArray( "one,two,three,one,one,three,two,four,two,two,four,four,four" );
counter = ArrayNew(1);
ArraySet( counter, 1, ArrayLen( array ), 1 );
query = QueryNew( '' );
QueryAddColumn( query, 'key', array );
QueryAddColumn( query, 'counter', counter );
</cfscript>

<cfquery name="sorted" dbtype="query">
SELECT key, sum(counter) AS total FROM query
GROUP BY key ORDER BY total DESC
</cfquery>

You now have a query of with the keys and the number of occurrences for each key. Do with this as you like.

@Matt

My solution was based off an earlier comment where Rich showed some code on how to create the unique key struct and maintain a count of how many times each duplicate was seen. Either way, looks like there's a couple of ways to get the same result.

Thanks Guys!

After hundreds of hairs being pulled out I finally figured it out.

I just have a few more things to do and my project will be 95.5 percent done.

Once again thanks for all the help here was my solution...

<!--- CONVERT THE SCRUB URL TO A LIST --->
<cfset convertResults_toList = ArrayToList(results_scrub_url) >

<!--- CREATE THE LIST FOR THE RESULTS || THIS LIST CONTAINS ONLY THE POSITION OF
THE ARRAY SO WE CAN THEN LOOP OVER THE LIST FOR APPRIPORATE RESULTS --->
<cfset finalResults_List = "">

<!--- NOW THAT THE SCRUBED URLS ARE CONVERTED TO A LIST WE CAN NOW DO A LOOP OVER THEM AND NOW COMPARE THEM --->
<!--- THE LOOP WILL PREPEND ( ADD TO THE END OF ) THE LIST WHICH THERITICALLY MEANS
THAT IT WILL ADD THE FIRST ONE TO THE START ETC... --->

<cfloop from="1" to="#arraylen(results_scrub_url)#" index="curRes">

<!--- THIS LOOP ALLOWS US TO LOOP OVER THE REMAINING RESULTS TO SEE
IF WE HAVE A MATCH IF WE HAVE A MATCH WE ARE GOING TO PREPEND THE RESULT TO THE LIST --->
<cfloop from="1" to="#arraylen(results_scrub_url)#" index="checkRes">

<!--- CHECKING CURRES (CURRENT RESULT) VS THE CHECKRES --->
<cfif results_scrub_url[curRes] eq results_scrub_url[checkRes] AND NOT curRes eq checkRes >

<cfif NOT listContains(finalResults_List, #curRes#) >
<!--- APPEND WHAT WE FOUND TO THE LIST --->
<cfset finalResults_List = ListAppend(finalResults_List, "#curRes#") >
</cfif>

</cfif>

</cfloop>

</cfloop>

Well Never Mind!

-- Ugh, I thought I finished it but it turns out its still kicking duplicates. It's going to be a simple fix. I will let you guys know.

@Jody

I can't seem to get your code sample to work. If you are still having problems, try this code out and see if it gets you what you wanted.

<!--- Comma delimited list with various duplicates --->
<cfset listWithDups = "second,second,second,third,third,first,first,first,first,fourth" />

<!--- Convert list to 1 column query var --->
<cfset query = queryNew("val") />
<cfloop list="#listWithDups#" index="i">
<cfset queryAddRow(query) />
<cfset querySetCell(query, "val", i) />
</cfloop>

<!--- Remove duplicates and sort results using query of query and "group by" --->
<cfquery name="sortedQuery" dbtype="query">
SELECT val, count(*) as numOcurrences
FROM query
GROUP BY val
ORDER BY numOcurrences desc, val asc
</cfquery>

<!--- Display sorted query --->
<cfdump var="#sortedQuery#" />

<!--- Convert sorted values to list --->
<cfset finalList = valueList(sortedQuery.val) />

<!--- Display final list --->
<cfdump var="#finalList#" />

@Jose Galdamez,

Oh heh yeah I didn't paste the whole code. I should have defined the vars -- my bad. It's fixed thou. Thanks.

How about http://www.iknowkungfoo.com/blog/index.cfm/2008/10/22/Remove-duplicate-list-or-array-elements-using-ColdFusion-and-Java which recommends using Java's LinkedHashSet for this purpose

Hello Ben.

No good :(
Gave me a "500 server internal error" on CF8 when playing this trick with list consisting of 1 element [37077015].
In all other cases it worked like a charm.
Think I'll have to try Java method instead :(

I believe the reason for the exception was not the list length but it's items. 37077015 is a big numeric value. Making a structure key from it might cause some problems.
Exception was 500 internal server error and then many encoded characters like "‹ ÅZ{sâ8 ÿ;SµßAÇ" :(

Here I am again, 4 years after you created this blog entry and it just helped me today! Thanks for all of your work for the Coldfusion community.

Ben, I used your method of removing duplicates again. I did it using CFSCRIPT this time. I figured I'd share it.

SecurityStruct = structNew();
for (i = 1; i lte listLen(SecurityList); i++) {
SecurityStruct[listGetAt(SecurityList, i)] = "";
}
SecurityList = StructKeyList(SecurityStruct);

Ben

This is just awesome! Great thinking outside of the box. Its powerful stuff like this that kicks the poo out of .Net

Thanks again!

Thanks for sharing. Nice, clean solution.

You are amazing. Thank you for all that you do!

Okay you just saved me a lot of time with an elegant solution. AGAIN!

Thanks!

Late to the party but figured I would add my two cents anyway.

How about a way to count the occurrences of each value in the list, before or during the conversion to a struct key list?

I would imagine that one would use listValueCount() (or listValueCountNoCase()), e.g.:

<cfset objMovies[ strMovie ] = listValueCount(lstMovies, strMovie) />

Not having actually tested it I'm not sure what it would add to the processing time.

Hi Ben. I ran across this post trying to find a solution to my problem of cleaning duplicates from a 2D array. I can't convert the array to a list because it is not 1D. Do you have any suggestions on how to do this for 2D arrays?
Thanks.

@Nina,

That's certainly an interesting one to solve. Does your 2D array have a consistent width for each row? What happens to the duplicate values? Do you set the cells to null?

@Jose,

No, the widths are not consistent for each row. Right now I am not doing anything with the duplicate values, they're just sitting there being duplicates (lol). I don't know how to get rid of them in the array is the reason.
The array is getting duplicate values because I have 2 different queries that are populating the array, each of which may be returning the same value, thus the duplicate.
I think I am just going to have to figure out a way to combine the queries, or maybe a way to make it a 1D array, get rid of dups, then go get the other data I need using the array value.

@Nina,

I'm wondering if something like this would work. What do you think?

If this is too inefficient maybe there's a way of doing a UNION on the queries and a GROUP BY on top of that UNION.

<cfscript>
var duplicateStruct = {};
var key = "";
 
// Loop through outer array
for (rowNum = 1; rowNum <= arrayLen(twoDArray); rowNum++) {
	// Loop through inner array
	for (colNum = 1; colNum <= arrayLen(twoDArray[rowNum]); colNum++) {
		key = twoDArray[rowNum][colNum];
 
		if (!structKeyExists(duplicateStruct, key)) {
			// First time seeing this key
			duplicateStruct[key] = 1;
		} else {
			// Keep count of how many times duplicate appears
			duplicateStruct[key]++;
 
			// Set array cell to null/undefined
			twoDArray[rowNum][colNum] = javaCast("null", 0);
		}
	}
}
</cfscript>

For those who end up here using Google and scroll all the way down, if you are using CF10, you can now use listRemoveDuplicates() to get a list without duplicates.