GNU bug report logs - #26540
25.2; [PATCH] Add cl-set-equal to test for set equality

Previous Next

Full log

View this message in rfc822 format

From: Michael Heerdegen <michael_heerdegen <at> web.de>
To: Damien Cassou <damien <at> cassou.me>
Cc: John Mastro <john.b.mastro <at> gmail.com>, Nicolas Petton <nicolas <at> petton.fr>, 26540 <at> debbugs.gnu.org
Subject: bug#26540: 25.2; [PATCH] Add cl-set-equal to test for set equality
Date: Wed, 19 Apr 2017 23:19:03 +0200

Damien Cassou <damien <at> cassou.me> writes:

> Damien Cassou <damien <at> cassou.me> writes:

> > it makes sense and I will try this way. Nevertheless, it also means
> > giving up on the :key feature. I guess it's ok.

OTOH I see no reason not to support it.  There is no reason to provide a
function in a library specializing on sequences with less features than
in some other lib.  Just my personal opinion.  Of course you can get the
effect of :key by adopting the TESTFN, but also note my other comment:

> here it is. Any feedback? 

It might be worth it to try to optimize things a bit for the most usual
TESTFNs `eq' and `equal'.  For example, try

#+begin_src emacs-lisp
(let ((s1 (number-sequence 1 10000))
      (s2 (number-sequence 1 10000)))
  (seq-set-equal s1 s2))
#+end_src

vs.

#+begin_src emacs-lisp
(let ((s1 (number-sequence 1 10000))
      (s2 (number-sequence 1 10000)))
  (seq-set-equal-2 s1 s2))
#+end_src

with this implementation using hash-tables:

#+begin_src emacs-lisp
(defun seq-set-equal-2 (sequence1 sequence2)
  (let ((table1 (make-hash-table :size (length sequence1)))
        (table2 (make-hash-table :size (length sequence2))))
    (seq-doseq (elt sequence1) (puthash elt t table1))
    (seq-doseq (elt sequence2) (puthash elt t table2))
    (and (seq-every-p (lambda (elt) (gethash elt table2)) sequence1)
         (seq-every-p (lambda (elt) (gethash elt table1)) sequence2))))
#+end_src

I guess other functions in seq.el could be optimized as well,
e.g. `seq-difference'.


Regards,

Michael.

Previous Next

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