我需要连接两个列表，对它们进行排序并删除重复项。有没有更好的方法来做这件事？

Question

我有两个未排序的列表，我需要生成另一个排序的列表，其中所有元素都是唯一的。

元素可以在两个列表中多次出现，并且它们最初是未排序的。

我的函数如下所示：

(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))))

有没有更好的方法来实现同样的目标？

示例调用：

[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

我们的邻居友好的Lisp专家指出了remove-duplicates function。

他还提供了以下代码片段：

(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

我想我会首先对两个列表分别排序，然后将它们合并到一个也可以跳过重复项的函数中。这应该会更快一点，因为它需要更少的遍历两个列表。

附言:我怀疑它能做得更快，因为你基本上总是需要至少一个排序和一个合并。也许您可以在一个函数中结合使用这两个函数，但如果这不会造成(很大的)差异，我也不会感到惊讶。

Answer 3

如果在合并列表之前对列表进行了排序，则可以同时合并、删除重复项和进行排序。如果它们已排序且无重复，那么merge/sort/duplicate-remove功能就变得非常简单。

实际上，更改插入函数可能会更好，这样它就可以执行排序插入来检查重复项。然后，您总是拥有没有重复项的排序列表，合并它们是一件微不足道的事情。

不过，您可能更喜欢使用快速插入函数，但代价是以后要对重复项进行排序/删除。