Re: remove-duplicates performances

[David Kastrup <dak@gnu.org>]

Thierry Volpiatto <thierry.volpiatto@gmail.com> writes:

> i just noticed that `remove-duplicates' is very slow.
>
> Something like below seem much faster:
>
> (defun* remove-dups (seq &key (test 'eq))
>   (let ((cont (make-hash-table :test test)))
>     (loop for elm in seq
>        unless (gethash elm cont)
>        do (puthash elm elm cont)
>        finally return (loop for i being the hash-values in cont collect i))))
>
> Test:
>
> (setq A (let ((seq (loop for i from 1 to 10000 collect i)))
>           (append seq seq)))
> (1 2 3 4 5 6 7 8 9 10 1 2 ...)
>
> (remove-dups A)
> (1 2 3 4 5 6 7 8 9 10 11 12 ...)
> elp-results: remove-dups    1           0.013707      0.013707
>
> (remove-duplicates A)
> (1 2 3 4 5 6 7 8 9 10 11 12 ...)
> elp-results: remove-duplicates  1           66.971619     66.971619
>
> Would be nice to improve performances of `remove-duplicates'.

There is little point in the overhead of a hashtable for a one-shot
operation.  Hashtables are best for _maintaining_ data, not for
processing other data structures.

I've found the following in some file of mine:

(defun uniquify (list predicate)
  (let* ((p list) lst (x1 (make-symbol "x1"))
	 (x2 (make-symbol "x2")))
    (while p
      (push p lst)
      (setq p (cdr p)))
;;;    (princ lst)(princ "\n")
    (setq lst
	  (sort lst `(lambda(,x1 ,x2)
		       (funcall ',predicate (car ,x1) (car ,x2)))))
;;; lst now contains all sorted sublists, with equal cars being
;;; sorted in order of increasing length (from end of list to start).
;;

    (while (cdr lst)
      (unless (funcall predicate (car (car lst)) (car (cadr lst)))
	(setcar (car lst) x1))
      (setq lst (cdr lst)))
    (delq x1 list)))

(uniquify '(2 1 2 1 2) '<)
(uniquify '(4 7 3 26 4 2 6 24 4 5 2 3 2 4 6) '<)

Obviously, this should make use of lexical binding "nowadays" instead of
creating its own unique symbols for function parameters.  And instead of
using x1 as a sentinel value some other unique thing might be used, like
a one-shot '(nil).

Basically, for a one-shot O(n^2) operation on a list, `sort' will
usually do the trick.  But if you are doing that O(n^2) operation
regularly, you should probably maintain the whole data set in a
hashtable instead.

-- 
David Kastrup