Ask Ben: Removing Duplicate List Items While Maintaining Original List Order
Posted January 15, 2009 at 9:50 AM by Ben Nadel
Do you know a way to remove duplicates from a list while keeping it sorted a-z? I have a list with the values I want and sorted correctly, but I have yet to find a way to sort it correctly. Any help would be great! Thanks!!
A while back, I described a very simple, elegant solution for using ColdFusion structs to remove duplicate values from a list. While nice, the limitations of that algorithm were that it did not ensure case sensitivity of the list items (depending on how you coded it) and it did not maintain any ordering of the original list. For the most part, I work with lists of IDs, so that was not a problem.
If we want to maintain the case sensitivity and ordering of the original list, we just need to add a little more logic to this idea. We can still use the ColdFusion struct as a look-up for our unique values; but, we will no longer use the struct to render our final list of unique values:
- <!--- Create a list with duplicate values. --->
- <cfset strList = "1,1,2,3,4,1,3,5,5,1,9,0,1" />
-
- <!---
- Create an look up index. This is a struct whose only
- purpose is to provide a fast key-lookup for existing values.
- --->
- <cfset objExistingKeys = {} />
-
- <!---
- We are going to create a new array to hold our "new" list
- values. This will be our ordered copy of the list with only
- unique values.
- --->
- <cfset arrNewList = [] />
-
- <!---
- Now, let's loop over the existing list and build our new
- list IN ORDER with only unique values.
- --->
- <cfloop
- index="strItem"
- list="#strList#"
- delimiters=",">
-
- <!--- Check to see if this item has been used already. --->
- <cfif NOT StructKeyExists( objExistingKeys, strItem )>
-
- <!---
- This list item is not a key in our look up index
- which means that it has NOT been used in our new
- list yet. Let's add it to our new list array.
- --->
- <cfset ArrayAppend( arrNewList, strItem ) />
-
- <!---
- Add the item to our look up index so that we don't
- use it again on further loop iterations.
- --->
- <cfset objExistingKeys[ strItem ] = true />
-
- </cfif>
-
- </cfloop>
-
- <!---
- Now that we have copied over all the unique values in
- order to our new list, let's collaps the array down into
- a string list.
- --->
- <cfset strNewList = ArrayToList( arrNewList ) />
-
- <!--- Output the new list. --->
- #strNewList#
As you can see, as we loop over our existing list, we are building a parallel list (using an array) with the unique values. Since both lists and arrays have inherent ordering, our use of ArrayAppend() maintains the order of the original list. Every time we hit a new unique value, we add it to our struct-look-up table to make sure that we never copy a duplicate value over to the new list.
When we run the above code, we get the following output:
1,2,3,4,5,9,0
The list is now composed of unique values in the original order. I am using an array and ArrayAppend() to build the new list rather than ListAppend() only because I have found arrays to be faster than string concatenation. Of course, for small lists, there would be zero difference in performance. I hope that helps.
Reader Comments
Thanks Ben, exactly what I needed!!
I use your structure dedupe idea and then just do a listsort to get the sorting correctly.
@Adam,
Awesome man, glad to help.
@Aaron,
That's a good idea as well. I guess when I read the question, I ignored the "a-z" part and just thought about the order of the original list. Nice catch.
Very very nice. I was a bit confused though when I read "The list is not composed of unique values in the original order" (emphasis added), and it took me a while to realize that you meant "... now composed ...." I guess I'm not quite awake yet.
@Matt,
Ooops. Good catch - typo fixed.
how about this:
// list with duplicate values.
strList = "1,1,2,3,4,1,3,5,5,1,9,0,1";
// new list to the copy that wont have dups
strNewList = "";
while (listLen(strList)) {
if (!listFind(strNewList,listFirst(strList))) strNewList = listAppend(strNewList,listFirst(strList));
strList = listRest(strList);
}
<cfoutput>#strNewList#</cfoutput>
You know, I just posted a method that uses listAppend instead of arrayAppend, and now I realize that you explained why you used the array instead of the list. Doh! My bad. You can delete my post if you like.
For your "How NOT to do it" file:
<cfset strList="1,1,2,3,4,1,3,5,5,1,9,0,1">
<cfset q=queryNew("item,position")>
<cfloop list="#strList#" index="j">
<cfset queryAddRow(q)>
<cfset querySetCell(q, "item", j, q.recordCount)>
<cfset querySetCell(q, "position", q.recordCount, q.recordCount)>
</cfloop>
<cfquery name="r" dbtype="query">
SELECT item, MIN(position) as firstPosition
FROM q
GROUP BY item
</cfquery>
<cfquery name="s" dbtype="query">
SELECT q.item, q.position
FROM q, r
WHERE (q.item = r.item) AND (q.position = r.firstPosition)
ORDER BY q.position
</cfquery>
<cfset strNewList=valueList(s.item)>
@Chris,
No worries my man. For small lists, the speed differences are not going to be noticeable.
@Rick,
If you want, I can set that algorithm up as a web service on my server and then you can modify your example to use CFHTTP to pass in the list and I'll return the unique version ;)
I could not resist -
Here is a version without cfloop based on java
It will allow you to retain the original list sort or to sort any way you want.
It is based on posts I have read from:
Adrian J. Moreno and Ben Nadel
Links to those posts are at the bottom
<cfset strList = "1,1,2,3,4,1,3,5,5,1,9,0,1" />
<cfset newListArray = listToArray( strList ) />
<cfset lhs = createObject("java", "java.util.LinkedHashSet") />
<cfset lhs.init( newListArray ) />
<!--- Clear out the original elements --->
<cfset newListArray.clear() />
<!--- Add all of the unique elements back from lhs --->
<cfset newListArray.addAll( lhs ) />
<!--- If you want to sort the array --->
<!--- either with Java --->
<cfset CreateObject( "java", "java.util.Collections" ).Sort( newListArray ) />
<!--- or with CF --->
<!--- <cfset temp = arraySort( newListArray,"numeric","asc") > --->
<!--- show the clean list --->
<cfoutput>#arrayToList( newListArray )#</cfoutput>
source posts:
http://www.iknowkungfoo.com/blog/index.cfm/2008/10/22/Remove-duplicate-list-or-array-elements-using-ColdFusion-and-Java
http://www.bennadel.com/blog/280-Randomly-Sort-A-ColdFusion-Array-Updated-Thanks-Mark-Mandel.htm
Or ...
http://wiki.openbluedragon.org/wiki/index.php/ListRemoveDuplicates()
Didn't like the () at the end of the last URL I posted, so let's try this:
http://tinyurl.com/a4oy3u
Ben said: "you can modify your example to use CFHTTP to pass in the list"
Well played, sir. Well played.
i did this for a couple of lists, just a little differently, but the results i think are the same. the lists were css and js files to be written to the document head, so the original order had to be maintained and the first occurrence of a duplicate had to remain. i did it by looping the list from end to start and setting the struct value to the index. then a numeric sort on the struct kept the original order. if you see any place this might fail, i'd be grateful to hear it.
<cfset objNoDupes = structNew()>
<cfloop from="#listlen( strList )#" to="1" step="-1" index="i">
<cfset objNoDupes[ listgetat( strList, i ) ] = i>
</cfloop>
<cfset strNewList = ArrayToList( structSort(objNoDupes, 'numeric') )>
@Jeff,
Good links. I always like learning about more Java-based methods (referring to the link that is not mine - Im not that big headed :)).
@Matt,
Ah, that makes it too easy.
@DB,
I don't think that one can maintain (or guarantee) the list order.
this is very similar to chris' example, but here it is anyway, and keeps order as well.
sz_List = '1,2,3,2,2,3,2,2,345,4324,23';
sz_ListNew = '';
for (i=1; i<= listLen(sz_List ); i++){
if(listFindNoCase(sz_listNew, listGetAt(sz_List , i)) == 0 )
sz_listNew = listAppend(sz_listNew, listGetAt(sz_List,i));
}
CFLib has a couple of similar functions. You would need to reorder by a separate function thogh.
http://cflib.org/udf/ListDeleteDuplicates
http://cflib.org/udf/ListDeleteDuplicatesNoCase
This method wont work if you need case sensitivity, since the struct key bins are case insensitive.
@Jon,
This is true. If you need case-sensitivity, I suppose you could go with ListFindNoCase() on the new list rather than using a struct. Not sure if the Java method that @Jeff mentions above will be case-sensitive.
@Ben, @Jon
Yes in the current format the Java solution is case sensitive.
The CF arraySort() will also sort the array "text" or "textnocase" so that you can really control the results should you want to sort them.
Nice.
once again , you saved me a bunch of time with this. thank yoouuu sir!
Awesome! Nice time saver and keeps the UI happy :) I had to drop this into a CF7 site and the only changes were StructNew() and ArrayNew(1) when creating, and it works great on CF7 (and I would assume before) too!
@Andrew,
Awesome, glad to help.
Thanks once again, Ben. This came in handy today, saved me a little stress.
@SuperAlly,
Boo ya!
Is it possible this solution doesn't works for Coldfusion MX7?
I get an error:
Invalid token '{' found on line 229 at column 82.
On the line: <cfset objExistingKeys = {} />
Might consider trim()ing up those structure keys at creation, as "Adobe Digital Editions"," Adobe Digital Editions" be not equal (of course). Chasing my tail, for bit I was. :)
Bob
Can be done in one readable line using Java (discounting the list setup below):
someList = "blah,blah,fubar,blah,fubar,hello,world";
uniqueArray = createObject("java", "java.util.LinkedHashSet").init(ListToArray(someList )).toArray();
The uniqueArray variable is now an array with the order maintained and duplicates removed.
Thanks Ben, this was exactly what I was looking for!
