我需要连接两个列表，对它们进行排序并删除重复项。有一个更好的方法吗？

StackOverflow https://stackoverflow.com/questions/100048

  •  01-07-2019
  •  | 
  •  

题

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

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

我的函数如下所示：

(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)
有帮助吗？

解决方案

我们邻居友好的 Lisp 大师指出 删除重复项功能.

他还提供了以下片段：

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

其他提示

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

附：我怀疑它是否可以更快地完成，因为您基本上总是需要至少一种排序和一种合并。也许你可以将两者结合在一个函数中，但如果这不会产生（大）差异，我不会感到惊讶。

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

事实上，最好更改插入函数，以便它执行检查重复项的排序插入。那么你总是拥有没有重复项的排序列表，并且合并它们是一件微不足道的事情。

话又说回来，您可能更喜欢快速插入功能，但代价是稍后排序/删除重复项。

如果在删除重复项之前应用排序，那么删除重复项功能不是会运行得更好吗？

正如 Antti 指出的那样，您可能希望利用 REMOVE-DUPLICATES 和 SORT，尽管我可能会为测试函数使用关键字（或可选参数）：（Defun Merge-Lists（List-1 List-2 sort-fn＆key（test＃'eql））...）或（Defun Merge-Lists（List-1 List-1 list-1 sort-fn＆optional（test＃'eql） ...）

这样，您就不必指定测试函数（REMOVE-DUPLICATES 使用它来测试“这些是否被视为重复项”），除非 EQL 不够好。

听起来你需要使用 Sets。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top