Re: remove-duplicates performances

[Thierry Volpiatto]

David Kastrup <address@hidden> writes:

> 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) '<)

This is nice and very instructive (at least for me) thanks.
It is not as performant as the version with hash-table, but very usable:
0.3 <=> 0.13 with same test on list with 20000 elements.
However, isn't it a problem when we want to remove duplicate in a list
type alist e.g ((a . 1) (b . 2) (a . 1) (c . 3) (b . 2)...)

-- 
A+ Thierry
Get my Gnupg key:
gpg --keyserver pgp.mit.edu --recv-keys 59F29997