时间戳

首页 > 解决方案 > 从 Common Lisp 中的列表中按值删除重复项

lisp - 从 Common Lisp 中的列表中按值删除重复项

问题描述

给定由以下格式的几个“对象”组成的两个列表：(name id)如何从第一个列表中获取与第二个列表不匹配的对象？

预期输出：

(remove-duplicates-by-name
  '((Oliver 1) (Charlie 2) (Oscar 20))
  '((Oliver 2)(Charlie 3)))

((Oscar 20))

(remove-duplicates-by-name 
  '((Oliver 1)) 
  '((Oliver 2)(Charlie 3)))

()

(remove-duplicates-by-name 
  '() 
  '((Oliver 2)(Charlie 3)))

()

编辑：

输出顺序很重要。例子：

(remove-duplicates-by-name 
  '((Oliver 1) (Charlie 2) (Oscar 20) (Daniel 30)) 
  '((Oliver 2)(Charlie 3)))

正确的输出：((Oscar 20)(Daniel 30))

输出错误：((Daniel 30)(Oscar 20))

标签： lispcommon-lisp

解决方案

这里有两个 hacky 解决方案。

(defun remove-duplicates-by-name (l to-remove)
  ;; low performance with large to-remove lists but fine with short
  ;; ones
  (loop for e in l
        unless (assoc (car e) to-remove)
        collect e))

(defun remove-duplicates-by-name (l to-remove)
  ;; high performance with large to-remove lists but consy and
  ;; probably slow with short ones
  (loop with dups = (loop with dt = (make-hash-table)
                          for e in to-remove
                          do (setf (gethash (car e) dt) t)
                          finally (return dt))
        for e in l
        unless (gethash (car e) dups)
        collect e))

推荐阅读