When TEST in DELETE-DUPLICATES (and REMOVE-DUPLICATES) is an acceptable
HASH-TABLE-TEST, DELETE-DUPLICATES can be linear:
CLLIB/math.lisp:
(defun count-all (seq &key (test 'eql) (key #'value) append weight
&aux (ht (or append (make-hash-table :test test))))
"Return the hash table with counts for values of the sequence."
(map nil (if weight
(lambda (el)
(incf (gethash (funcall key el) ht 0)
(funcall weight el)))
(lambda (el) (incf (gethash (funcall key el) ht 0))))
seq)
ht)
(defun duplicates-delete (seq)
"linear DELETE-DUPLICATES"
(let ((ht (cllib:count-all seq :test 'eq :key #'identity)))
(delete-if-not (lambda (x) (zerop (decf (gethash x ht)))) seq)))
--
Sam Steingold (http://www.podval.org/~sds) running w2k
<http://www.camera.org> <http://www.iris.org.il> <http://www.memri.org/>
<http://www.mideasttruth.com/> <http://www.honestreporting.com>
Whom computers would destroy, they must first drive mad.
