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 produce another list which is sorted and where all the elements are unique.

The elements can occur multiple times in both lists and they are originally 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?

Sample call:

[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

I think I would first sort the two lists separately and then merge them with a function that also skips over duplicates. This should be a bit faster as it requires one less traversal of both lists.

P.S.: I doubt it can be done much faster as you basically always need at least one sort and one merge. Perhaps you can combine both in one function, but I wouldn't be surprised if that doesn't make a (big) difference.

Answer 2

Sounds like you need to be using Sets.

Answer 3

Our neighbourhood friendly Lisp guru pointed out 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 4

If the lists are sorted before you merge them, they can be merged, duplicate-removed and sorted at the same time. If they are sorted AND duplicate-free, then the merge/sort/duplicate-remove function becomes really trivial.

In fact, it might be better to change your insert function so that it performs a sorted insertion that checks for duplicates. Then you always have sorted lists that are free of duplicates, and merging them is a trivial matter.

Then again, you might prefer to have a fast insert function at the cost of sorting/removing duplicates later on.

Answer 5

Wouldn't the remove-duplicates function operate better if the sort was applied before the remove-duplicates?

Answer 6

As Antti pointed out, you probably want to leverage REMOVE-DUPLICATES and SORT, though I'd probably use a 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) ...)

This way, you won't have to specify the test function (used by REMOVE-DUPLICATES to test for "is these considered duplicates"), unless EQL is not good enough.