Sam Steingold wrote:
> 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)))
I've thought the various list-set functions should take
a (nonstandard) keyword argument, MARK. This argument would
be a function of two arguments:
(1) On one argument, it would return a mark value associated
with the argument (which is a list element),
(2) On two arguments, it would set the mark value of the first
element to be true if the second argument is true, and NIL
if the second argument is false.
With this argument the various list-set operations could be performed
in linear time.
Paul
