作者:SU大肥婆_545 | 来源:互联网 | 2022-10-21 14:51
Common Lisp序列函数remove-duplicates
在每个多重性后面都保留一个元素。以下类似功能的目标remove-equals
是删除所有重复项。
但是,我想使用内置函数remove-if
(而不是迭代)和SBCL的哈希表功能用于:test函数,以将时间复杂度保持在O(n)。迫在眉睫的问题是SBCL相等性测试需要是全局的,但是该测试还需要依赖于的key
参数remove-equals
。可以满足两个要求吗?
(defun remove-equals (sequence &key (test #'eql) (start 0) end (key #'identity))
"Removes all repetitive sequence elements based on equality test."
#.(defun equality-test (x y)
(funcall test (funcall key x) (funcall key y)))
#.(sb-ext:define-hash-table-test equality-test sxhash)
(let ((ht (make-hash-table :test #'equality-test)))
(iterate (for elt in-sequence (subseq sequence start end))
(incf (gethash (funcall key elt) ht 0)))
(remove-if (lambda (elt)
(/= 1 (gethash elt ht)))
sequence :start start :end end :key key)))
Sylwester..
6
第三个参数将define-hash-table-test
测试与哈希函数相关联。使用会sxhash
破坏目的,因为应该针对test
功能进行调整。(equal x y)
暗示(= (sxhash x) (sxhash))
。因此,第二参数应该是一个函数test-hash
,使得(funcall test x y)
暗示(= (test-hash x) (test-hash y))
。仅具有测试功能是不可能做到这一点的。最好通过记录它需要散列支持来规避整个过程:
(defun remove-duplicated (sequence &key (test #'eql) (start 0) end (key #'identity))
"Removes all repetitive sequence elements based on equality test.
equalily tests other than eq, eql, equal and equalp requires you
add it to be allowed in a hash table eg. sb-ext:define-hash-table-test in SBCL"
(let ((ht (make-hash-table :test test)))
(iterate (for elt in-sequence (subseq sequence start end))
(incf (gethash (funcall key elt) ht 0)))
(remove-if (lambda (elt)
(/= 1 (gethash elt ht)))
sequence :start start :end end :key key)))
现在,如果用户需要自定义测试,则需要自己进行:
(defun car-equals (a b)
(equal (car a) (car b)))
(defun car-equals-hash (p)
(sxhash (car p)))
(sb-ext:define-hash-table-test car-equals car-equals-hash)
(car-equals '(1 2 3 4) '(1 3 5 7)) ; ==> t
(defparameter *ht* (make-hash-table :test 'car-equals))
(setf (gethash '(1 2 3 4) *ht*) 'found)
(gethash '(1 3 5 7) *ht*) ; ==> found
(remove-duplicated '((5 0 1 2) (5 1 2 3) (5 1 3 2) (5 2 3 4))
:test #'car-equals
:key #'cdr)
; ==> ((5 0 1 2) (5 2 3 4))
Rainer Joswi..
5
像这样的带有读取时间计算函数的东西将无法满足您的要求。从您的代码简化:
(defun foo (a b test)
#.(defun equality-test (x y)
(funcall test x y))
(funcall #'equality-test a b))
这是行不通的。
原因1:读取时创建的函数无法从周围的代码访问词法变量(此处无法引用test
,因为foo
在读取过程中不存在带有函数的环境)
test
内部的变量equality-test
不引用词法变量。未定义/未声明。
原因2:DEFUN评估为符号
阅读并评估读取时间代码后,代码如下所示:
(defun foo (a b test)
equality-test
(funcall #'equality-test a b))
好吧,equality-test
是一个未绑定的变量。这是运行时错误。
原因3:该功能equality-test
可能不存在
如果我们使用文件编译器来编译代码,则该函数equality-test
是在读取表单时在编译时环境内创建的,但它不会成为已编译代码的一部分。
1> Sylwester..:
第三个参数将define-hash-table-test
测试与哈希函数相关联。使用会sxhash
破坏目的,因为应该针对test
功能进行调整。(equal x y)
暗示(= (sxhash x) (sxhash))
。因此,第二参数应该是一个函数test-hash
,使得(funcall test x y)
暗示(= (test-hash x) (test-hash y))
。仅具有测试功能是不可能做到这一点的。最好通过记录它需要散列支持来规避整个过程:
(defun remove-duplicated (sequence &key (test #'eql) (start 0) end (key #'identity))
"Removes all repetitive sequence elements based on equality test.
equalily tests other than eq, eql, equal and equalp requires you
add it to be allowed in a hash table eg. sb-ext:define-hash-table-test in SBCL"
(let ((ht (make-hash-table :test test)))
(iterate (for elt in-sequence (subseq sequence start end))
(incf (gethash (funcall key elt) ht 0)))
(remove-if (lambda (elt)
(/= 1 (gethash elt ht)))
sequence :start start :end end :key key)))
现在,如果用户需要自定义测试,则需要自己进行:
(defun car-equals (a b)
(equal (car a) (car b)))
(defun car-equals-hash (p)
(sxhash (car p)))
(sb-ext:define-hash-table-test car-equals car-equals-hash)
(car-equals '(1 2 3 4) '(1 3 5 7)) ; ==> t
(defparameter *ht* (make-hash-table :test 'car-equals))
(setf (gethash '(1 2 3 4) *ht*) 'found)
(gethash '(1 3 5 7) *ht*) ; ==> found
(remove-duplicated '((5 0 1 2) (5 1 2 3) (5 1 3 2) (5 2 3 4))
:test #'car-equals
:key #'cdr)
; ==> ((5 0 1 2) (5 2 3 4))
2> Rainer Joswi..:
像这样的带有读取时间计算函数的东西将无法满足您的要求。从您的代码简化:
(defun foo (a b test)
#.(defun equality-test (x y)
(funcall test x y))
(funcall #'equality-test a b))
这是行不通的。
原因1:读取时创建的函数无法从周围的代码访问词法变量(此处无法引用test
,因为foo
在读取过程中不存在带有函数的环境)
test
内部的变量equality-test
不引用词法变量。未定义/未声明。
原因2:DEFUN评估为符号
阅读并评估读取时间代码后,代码如下所示:
(defun foo (a b test)
equality-test
(funcall #'equality-test a b))
好吧,equality-test
是一个未绑定的变量。这是运行时错误。
原因3:该功能equality-test
可能不存在
如果我们使用文件编译器来编译代码,则该函数equality-test
是在读取表单时在编译时环境内创建的,但它不会成为已编译代码的一部分。