Subject: Re: bug#26540: 25.2; [PATCH] Add cl-set-equal to test for set equality

From: Michael Heerdegen <[email-masked]>
Date: Thu, 11 May 2017 21:42:46 +0200

Damien Cassou <[email-masked]> 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.