[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
bug#26540: 25.2; [PATCH] Add cl-set-equal to test for set equality
From: |
Michael Heerdegen |
Subject: |
bug#26540: 25.2; [PATCH] Add cl-set-equal to test for set equality |
Date: |
Thu, 11 May 2017 21:42:46 +0200 |
User-agent: |
Gnus/5.13 (Gnus v5.13) Emacs/26.0.50 (gnu/linux) |
Damien Cassou <damien@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.