6

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

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

我的功能如下所示：

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

6 回答 6

11

我们邻里友好的 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))
于 2008-09-19T06:49:24.113 回答
1

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

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

于 2008-09-19T06:38:58.743 回答
1

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

事实上，最好更改您的插入函数，以便它执行检查重复项的排序插入。然后你总是有没有重复的排序列表，合并它们是一件小事。

再说一次，您可能更喜欢以稍后排序/删除重复项为代价的快速插入功能。

于 2008-09-19T06:54:28.767 回答
0

如果在删除重复项之前应用排序，删除重复项功能是否会更好地运行？

于 2008-09-19T10:46:52.267 回答
0

正如 Antti 指出的那样，您可能想要利用 REMOVE-DUPLICATES 和 SORT，尽管我可能会为测试函数使用关键字（或可选参数）：(defun merge-lists (list-1 list-2 sort-fn &key (test #'eql)) ...) 或 (defun 合并列表 (list-1 list-2 sort-fn &optional (test #'eql) ...)

这样，您不必指定测试函数（由 REMOVE-DUPLICATES 用于测试“这些被认为是重复的”），除非 EQL 不够好。

于 2008-11-06T12:05:50.333 回答
-2

听起来你需要使用 Sets。

于 2008-09-19T06:44:06.547 回答