Re: remove-duplicates performances

[David Kastrup]

Thierry Volpiatto <address@hidden> writes:

> 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,

Well, the sorting function is a mess due to not being compiled and
fearing dynamic binding.  If you byte-compile something like

(defun uniquify (list predicate)
  (let* ((p list) lst (sentinel (list nil)))
    (while p
      (push p lst)
      (setq p (cdr p)))
    (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) sentinel))
      (setq lst (cdr lst)))
    (delq sentinel list)))

the behavior is likely better.

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

Why?  You need a predicate < both for sorting and for telling
inequality.  As long as you define a suitable predicate for that
purpose, what should go wrong?  Any elements for which
(or (predicate a b) (predicate b a)) is nil will be considered
duplicate.

-- 
David Kastrup