bug#10386: CODE wishlist: íncludedelete-duplicates.el

["Drew Adams" <drew.adams@oracle.com>]

> >     http://mwolson.org/static/dist/elisp/delete-duplicates.el
> 
> This is already provided in Emacs24+.

`delete-dups' has been in Emacs since Emacs 22, actually.

> What is not provided is a fast version of remove-duplicates.
> http://article.gmane.org/gmane.emacs.devel/139546/match=remove+dups

+1

And the cl-seq.el version of `remove-duplicates' is *particularly* slow.  Even a
classic list dups removal algorithm is much faster.

Here's a comparison using `equal' and a list of strings (`elp-results'):

hash-remove-dups     1           0.031         0.031
list-remove-dups     1           5.813         5.813
remove-duplicates    1           122.875       122.875

Where:

(defun list-remove-dups (list)
  (let ((tail  list)
        new)
    (while tail
      (unless (member (car tail) new) (push (car tail) new))
      (pop tail))
    (nreverse new)))

(defun* hash-remove-dups (seq &key (test 'equal))
  (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))))

With all 3 functions byte-compiled, using these calls:

(hash-remove-dups    B :test 'equal)
(list-remove-dups    B) ; uses `equal'
(remove-duplicates   B :test 'equal)

And with this list B (initialized anew each time):

(let ((seq (loop for i from 1 to 10000
             collect
             (format "%s" (random most-positive-fixnum)))))
  (append seq seq))

With B 10 times smaller (1000):

hash-remove-dups     1           0.0           0.0
list-remove-dups     1           0.047         0.047
remove-duplicates    1           1.172         1.172

With B 10 times bigger (100000), the difference between hash and classic list is
even greater (fuggedabowt cl-seq's `remove-duplicates' in this case):

hash-remove-dups     1           0.359         0.359
list-remove-dups     1           1209.578      1209.578
remove-duplicates    la-la...