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 回答