为什么union不返回一个唯一的列表？

Question

为什么Hyperspec中的以下语句是这样的，有什么逻辑原因吗？如果list-1和list-2之间存在重复，则结果中只有一个重复的实例。如果list-1或list-2中有重复的条目，则冗余条目可能会出现在结果中，也可能不会出现。

在我读到这篇文章之前，我一直认为联合应该返回一个唯一的列表，并对我的代码为什么没有这样做感到沮丧。在列表之间而不是在列表内删除重复项似乎也很奇怪。为什么要指定这一点呢？

似乎应该能够假设联合将生成集合元素的唯一列表，或者我是否遗漏了什么？

有关Hyperspec的完整页面，请参阅http://clhs.lisp.se/Body/f_unionc.htm

Answer 1

如果您的代码只包含唯一元素的集合(如1 2 3 )，则UNION将保留此属性。

如果您的代码包含具有非惟一元素的集合(如1 2 2 3 )，则UNION不需要在结果集中强制实现唯一性。

删除重复项是通过一个单独的函数来完成的：REMOVE-DUPLICATES。

Answer 2

假设两个列表中作为UNION参数的元素都是唯一的，这意味着算法在最坏情况下(不可排序、不可哈希的元素)的复杂度为O(n*m)。另一方面，在这种情况下，删除列表中的重复项需要O(n^2)。即使在没有重复的情况下，让UNION删除重复项也会使运行时间增加大约三倍，因为大部分时间都被比较所消耗。