Re: What to do for faster `remove-duplicates'?

[Oleh Krehel <ohwoeowho@gmail.com>]

Artur Malabarba <bruce.connor.am@gmail.com> writes:

> But that nreverse could be optimized out if the first loop followed a
> `while'+`setcdr' strategy like the second.

Please check the optimized version:

(defun delete-dups (list)
  "Destructively remove `equal' duplicates from LIST.
Store the result in LIST and return it.  LIST must be a proper list.
Of several `equal' occurrences of an element in LIST, the first
one is kept."
  (if (> (length list) 100)
      (let ((hash (make-hash-table :test #'equal)))
        (let ((tail list)
              elt retail)
          (while (setq retail (cdr tail))
            (setq elt (car retail))
            (if (gethash elt hash)
                (setcdr tail (cdr retail))
              (puthash elt t hash))
            (setq tail retail))))
    (let ((tail list))
      (while tail
        (setcdr tail (delete (car tail) (cdr tail)))
        (setq tail (cdr tail)))))
  list)

Oleh