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

Previous Next

Full log

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

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: Re: bug#26540: 25.2; [PATCH] Add cl-set-equal to test for set equality
Date: Thu, 11 May 2017 21:42:46 +0200

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

> > [...] 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 
>
> as far as I can tell, little effort has been put in optimizing seq.el
> the way you describe it so I guess such an implementation of
> seq-set-equal would feel a bit alien in the current code
> base. Moreover, is your implementation faster on very small sets?

Probably not.  It was just a demonstration.

> Finally, making your implementation of seq-set-equal accepting a
> TESTFN parameter would be a bit complex as you would have to pass that
> to `make-hash-table` which also requires a hash function. 

Yes, we would have to limit TESTFN to functions that are implemented as
hash table test functions.

I took the idea from `delete-dups' btw, which is optimized with hash
tables for large lists.  We allow arbitrary TESTFNs in
`seq-set-equal-p', though, in practice and with :key functions allowed,
I would expect that supporting `eq' and `equal' would cover most use
cases.  For the rest, we could still fall back to the current
implementation.


Michael.

Previous Next

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