bug#10386: CODE wishlist: ínclude delete-duplicates.el

bug#10386: CODE wishlist: ínclude delete-duplicates.el

[Jari Aalto]

Package: emacs
Version: 23.3
Severity: wishlist

I come accross library functions that might be useful to be included in
Emacs:

    http://mwolson.org/static/dist/elisp/delete-duplicates.el

Jari

-- System Information
Debian Release: wheezy/sid
  APT Prefers testing
  APT policy: (500, testing) (990, unstable)
Architecture: i386
Kernel: Linux cante 3.1.0-1-686-pae #1 SMP Sun Dec 11 20:40:16 UTC 2011 i686 GNU/Linux
Locale: LANG=en_US.UTF-8

-- Versions of packages `emacs depends on'.
Depends:
emacs23         23.3+1-4        GNU Emacs is the extensible self-documenting 
emacs23-lucid   23.3+1-4        GNU Emacs is the extensible self-documenting 
emacs23-nox     23.3+1-4        GNU Emacs is the extensible self-documenting 

bug#10386: CODE wishlist: ínclude delete-duplicates.el

[Thierry Volpiatto]

Jari Aalto <jari.aalto@cante.net> writes:

> Package: emacs
> Version: 23.3
> Severity: wishlist
>
> I come accross library functions that might be useful to be included in
> Emacs:
>
>     http://mwolson.org/static/dist/elisp/delete-duplicates.el

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

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

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

[Drew Adams]

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

bug#10386: CODE wishlist: ínclude delete-duplicates.el

[Glenn Morris]

tags 10386 wontfix
stop

Jari Aalto wrote:

> I come accross library functions that might be useful to be included in
> Emacs:
>
>     http://mwolson.org/static/dist/elisp/delete-duplicates.el

The first line says:

  ;; Scraps of code having to do with deletion that I never ended up
  ;; using anywhere.

which is not inspiring. It has just 3 functions:

delete-from-list, which offers the same functionality as cl-seq's delete-if
delete-duplicates, which offers the same functionality as cl-seq's
  function of the same name (see also subr's delete-dups)
and alist-disjoint, which does not seem especially useful ("Remove each
key in KEYS from ALIST")

So I don't see anything worth adding here.