I need to join two lists, sort them and remove duplicates. Is there a better way to do this?

Question

I have two unsorted lists, and I need to create another list that is sorted and where all the elements are unique.

Elements can occur several times in both lists, and they are initially unsorted.

My function looks like this:

(defun merge-lists (list-a list-b sort-fn) "Merges two lists of (x, y) coordinates sorting them and removing dupes" (let ((prev nil)) (remove-if (lambda (point) (let ((ret-val (equal point prev))) (setf prev point) ret-val)) (sort (merge 'list list-a list-b sort-fn) ;' sort-fn)))) 

Is there a better way to achieve the same?

Call example:

 [CL]> (merge-lists '(9 8 4 8 9 7 2) '(1 7 3 9 2 6) #'>) ==> (9 8 7 6 4 3 2 1) 

Answer 1

Our neighbor guru Lisp pointed to the remove-duplicates function .

He also provided the following snippet:

 (defun merge-lists (list-a list-b sort-fn test-fn) (sort (remove-duplicates (append list-a list-b) :test test-fn) sort-fn)) 

Answer 2

I think I first sorted the two lists separately, and then combined them with a function that also skips duplicates. This should be a little faster, as it requires less crawl of both lists.

PS: I doubt that this can be done much faster since you basically always need at least one sort and one merge. You may be able to combine both in one function, but I won’t be surprised if it doesn’t make a (big) difference.

Answer 3

If the lists are sorted before they are combined, you can combine them, remove duplicates, and sort at the same time. If they are sorted and do not contain duplicates, the merge / sort / duplicate-remove function becomes really trivial.

In fact, it might be better to change the insert function so that it performs a sorted insert that checks for duplicates. Then you always have sorted lists that do not contain duplicates, and merging them is a trivial matter.

Then, you might want to have a quick insert function by sorting / deleting duplicates later.

Answer 4

Would the remove-duplicates function work better if sorting was applied before the duplicate removal?

Answer 5

As Antti noted, you probably want to use REMOVE-DUPLICATES and SORT, although I would probably use the keyword (or optional argument) for the test function: (defun merge-lists (list-1 list-2 sort-fn & key (test # 'eql)) ...) or (defun merge-lists (list-1 list-2 sort-fn & optional (test #' eql) ...)

That way, you won’t need to specify a test function (used by REMOVE-DUPLICATES to check for “these are read duplicates”) if EQL is not good enough.

Answer 6

Sounds like you need to use Sets.