检查列表是否包含重复项的谓词

Question

我正在尝试编写一个接受列表的函数，returns如果它包含重复条目则为 true，否则为 false。我知道我应该使用 member。这是我到目前为止的尝试（失败）：

(defun dupl (lst)
  (if (null lst) '())
  (if ((member (car lst) (cdr lst)) (cons (car lst) (dupes (cdr lst))))
    (t (dupl (cdr lst)))))

Answer 1

您的代码中存在一些问题。

第一个 if 应该使用 return-from 实际 return 值。最好使用 nil 而不是 '().
在第二个 if 中，您正在尝试使用 cond 语法。
我什至不确定你想用 cons 实现什么，但这似乎没有必要。

修复这些后，您的代码将如下所示：

(defun dupl (lst)
  (if (null lst) (return-from dupl nil))
  (if (member (car lst) (cdr lst)) 
      t
      (dupl (cdr lst))))

将两个 if 变成一个 cond 可能更简洁：

(defun dupl (lst)
  (cond ((null lst) nil)
        ((member (car lst) (cdr lst)) t)
        (t (dupl (cdr lst)))))

Answer 2

如果一个函数returns是一个布尔值，它很可能可以表示为一个布尔表达式。以下二次版本是一个可能的实现：

(defun duplicatesp (list &key (test #'eql))
  (and list
       (or (member (first list) (rest list) :test test)
           (duplicatesp (rest list) :test test))))

随后的懒程序员版本也可以解决问题：

(defun duplicatesp (list)
  (not (equal (remove-duplicates list) list)))

您也可以先对列表的副本进行排序，以获得更好的 O(n.log(n)).

时间复杂度

Answer 3

Common Lisp 中的许多函数使用 generalized booleans，根据 nil（空列表）是 false，并且其他一切都是 true:

Type BOOLEAN

… Conditional operations, such as if, permit the use of generalized booleans, not just booleans; any non-nil value, not just t, counts as true for a generalized boolean. However, as a matter of convention, the symbol t is considered the canonical value to use even for a generalized boolean when no better choice presents itself.

注意使用 t 的注释 "when no better choice presents itself." 将 return 广义布尔值 return 其他部分的函数制作出来通常很有帮助有用信息的真实价值。例如，member return 是列表的尾部，其第一个元素是正在检查成员资格的元素。在这种情况下，return 关联列表将重复元素映射到它们在列表中出现的次数可能很有用。

这是一种方法。它首先遍历列表，构建列表的唯一（根据 test and key arguments）元素的散列 table，将每个元素映射到它出现的次数。然后，通过散列 table 来构建所有出现不止一次的元素的关联列表。

(defun contains-duplicates (list &key (test 'eql) (key 'identity))
  "Returns an association list mapping duplicated elements to the
number of times that they appear in LIST.  TEST is a comparison
operator used to determine whether two elements are the same, and must
be acceptable as a test argument to MAKE-HASH-TABLE.  KEY is used to
extract a value from the elements of LIST, and the extracted values
are compared and returned in the result."
  (let ((table (make-hash-table :test test))
        (result '()))
    (dolist (x list)
      (incf (gethash (funcall key x) table 0)))
    (maphash #'(lambda (key count)
                 (unless (eql 1 count)
                   (push (cons key count) result)))
             table)
    result))

(contains-duplicates '(1 1 2 3 4 4 4))
;;=> ((4 . 3) (1 . 2))

(contains-duplicates '(1 2 3 4)) ; no duplicates 
;;=> NIL

(contains-duplicates '("A" "a" b a) :test 'equal :key 'string)
;;=> (("A" . 2))

(contains-duplicates '("A" "a" b a) :test 'equal :key 'string) ; "A" ~ a, but not "a"
;;=> (("A" . 2))

(contains-duplicates '("A" "a" b a) :test 'equalp :key 'string) ; "A" ~ "a" ~ a
;;=> (("A" . 3))

(contains-duplicates '(1 2 3 5) :key 'evenp) ; two even elements
;;=> ((NIL . 2))

Answer 4

只是我对效率的两分钱。如果您使用 memberp 来测试重复项，那么您将每个元素与其他元素进行比较，复杂度为 O(N^2)。 Joshua 在他的回答中建议使用散列 table 来测试重复项，这将以 space 为代价给出线性运行时间 O(N)。对于较小的列表，它也可能更慢。最后，如果您的列表可以排序，那么您应该得到 O(N.log(N)) 作为 coredump- 提及。这是一个使用 sort 测试 numeric 列表中的重复项的示例。（这是一个破坏性的功能。）

(defun duplicatesp (list)
  (mapl (lambda (cdr) (if (eql (first cdr) (second cdr))
                          (return-from duplicatesp T)))
   (sort list '<)) nil)

更新

出于好奇，我测量了建议答案在最坏情况下的表现（几乎没有重复）。因此，100 万次尝试 10 个元素的列表：

使用 member（Jan 的回答）：1.139 秒；
使用 hash-table（Joshua 的回答）：1.436 秒；
使用 sort（见上文，但首先复制列表）：1.484 秒。

因此，与小型列表没有区别。有趣的是，使用散列 table 有一些损失，但非常小。让我们对包含 1000 个元素的列表进行 1000 次尝试：

使用 member：9.968 秒；
使用 hash-table：0.234 秒；
使用 sort：0.390 秒。

正如预期的那样，使用 member 具有更高的复杂性。在此列表大小下，排序和散列之间的区别是不可见的。让我们对包含 1,000,000 个元素的列表进行 10 次尝试：

使用 hash-table：3.214 秒；
使用 sort：9.296 秒。

因此，sort 仍然相当不错，但正在放缓。这是我用来分析功能的简单代码：

(defun random-list (length)
  (loop for i from 0 below length collecting
       (random (expt 10 10))))

(defun random-collection (length tries)
  (loop for i from 0 below tries collecting
       (random-list length)))

(defun test-duplicates (function &key length tries)
  (let ((rc (random-collection length tries)))
    (time (mapc function rc))
    nil))

(test-duplicates #'dp_hash :length 1000000 :tries 10)
;etc.

检查列表是否包含重复项的谓词

Predicate that checks whether a list contains duplicates

lisp

clisp

list

common-lisp

Type BOOLEAN