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

Previous Next

To add a comment to this bug, you must first unarchive it, by sending
a message to control AT debbugs.gnu.org, with unarchive 10386 in the body.
You can then email your comments to 10386 AT debbugs.gnu.org in the normal way.

Toggle the display of automated, internal messages from the tracker.

Message #5 received at submit <at> debbugs.gnu.org (full text, mbox):

From: Jari Aalto <jari.aalto <at> cante.net>
To: submit <at> debbugs.gnu.org
Cc: mwolson <at> gnu.org
Subject: CODE wishlist: ínclude delete-duplicates.el
Date: Wed, 28 Dec 2011 09:55:38 +0200

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 

Message #8 received at submit <at> debbugs.gnu.org (full text, mbox):

From: Thierry Volpiatto <thierry.volpiatto <at> gmail.com>
To: bug-gnu-emacs <at> gnu.org
Cc: Jari Aalto <jari.aalto <at> cante.net>
Subject: Re: bug#10386: CODE wishlist: ínclude
	delete-duplicates.el
Date: Wed, 28 Dec 2011 10:09:46 +0100

Jari Aalto <jari.aalto <at> 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 

Message #11 received at 10386 <at> debbugs.gnu.org (full text, mbox):

From: "Drew Adams" <drew.adams <at> oracle.com>
To: "'Thierry Volpiatto'" <thierry.volpiatto <at> gmail.com>,
	<10386 <at> debbugs.gnu.org>
Cc: 'Jari Aalto' <jari.aalto <at> cante.net>
Subject: RE: bug#10386: CODE wishlist: íncludedelete-duplicates.el
Date: Wed, 28 Dec 2011 08:56:48 -0800

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

Message #18 received at 10386-done <at> debbugs.gnu.org (full text, mbox):

From: Glenn Morris <rgm <at> gnu.org>
To: 10386-done <at> debbugs.gnu.org
Subject: Re: bug#10386: CODE wishlist: ínclude
	delete-duplicates.el
Date: Wed, 11 Jan 2012 03:47:57 -0500

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.

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.