From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED!not-for-mail From: Michael Heerdegen Newsgroups: gmane.emacs.bugs Subject: bug#26540: 25.2; [PATCH] Add cl-set-equal to test for set equality Date: Thu, 11 May 2017 21:42:46 +0200 Message-ID: <87o9uzi3ih.fsf@drachen> References: <87bmrve6n9.fsf@cassou.me> <87vaq0hh3f.fsf@petton.fr> <87wpag8yog.fsf@cassou.me> <87tw5k8w4g.fsf@cassou.me> <87lgqwdrjs.fsf@drachen> <87d1bqt78a.fsf@cassou.me> NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: text/plain X-Trace: blaine.gmane.org 1494531802 27700 195.159.176.226 (11 May 2017 19:43:22 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Thu, 11 May 2017 19:43:22 +0000 (UTC) User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/26.0.50 (gnu/linux) Cc: John Mastro , Nicolas Petton , 26540@debbugs.gnu.org To: Damien Cassou Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Thu May 11 21:43:18 2017 Return-path: Envelope-to: geb-bug-gnu-emacs@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by blaine.gmane.org with esmtp (Exim 4.84_2) (envelope-from ) id 1d8tzX-00070k-DB for geb-bug-gnu-emacs@m.gmane.org; Thu, 11 May 2017 21:43:15 +0200 Original-Received: from localhost ([::1]:49894 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1d8tzd-0007eH-0F for geb-bug-gnu-emacs@m.gmane.org; Thu, 11 May 2017 15:43:21 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:44840) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1d8tzP-0007bh-LV for bug-gnu-emacs@gnu.org; Thu, 11 May 2017 15:43:08 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1d8tzK-0004Rq-NK for bug-gnu-emacs@gnu.org; Thu, 11 May 2017 15:43:07 -0400 Original-Received: from debbugs.gnu.org ([208.118.235.43]:36404) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1d8tzK-0004RM-JL for bug-gnu-emacs@gnu.org; Thu, 11 May 2017 15:43:02 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1d8tzK-0004yo-AI for bug-gnu-emacs@gnu.org; Thu, 11 May 2017 15:43:02 -0400 X-Loop: help-debbugs@gnu.org Resent-From: Michael Heerdegen Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Thu, 11 May 2017 19:43:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 26540 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: patch Original-Received: via spool by 26540-submit@debbugs.gnu.org id=B26540.149453178019131 (code B ref 26540); Thu, 11 May 2017 19:43:02 +0000 Original-Received: (at 26540) by debbugs.gnu.org; 11 May 2017 19:43:00 +0000 Original-Received: from localhost ([127.0.0.1]:39081 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1d8tzI-0004yV-10 for submit@debbugs.gnu.org; Thu, 11 May 2017 15:43:00 -0400 Original-Received: from mout.web.de ([212.227.17.11]:57346) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1d8tzG-0004yG-N5 for 26540@debbugs.gnu.org; Thu, 11 May 2017 15:42:59 -0400 Original-Received: from drachen.dragon ([92.208.83.149]) by smtp.web.de (mrweb102 [213.165.67.124]) with ESMTPSA (Nemesis) id 0Lba7D-1dtk2u2JIJ-00lAZY; Thu, 11 May 2017 21:42:39 +0200 In-Reply-To: <87d1bqt78a.fsf@cassou.me> (Damien Cassou's message of "Wed, 03 May 2017 15:12:05 +0200") X-Provags-ID: V03:K0:181FzHrtGRm5x73JUC/VU8HUgtaULdGmDCpSO0NNEVOYGKwUn/W 049BUMA23W8KvAn5bP52UBmFYcsr5tctb1Y7s4vxkyOgeK+t9lNqCwT9sHAyLUUx4Pbdx55 3uW3PH+AmfVv/VWEEvyoCQTkIJJg6YwgNDSPZRyQ9UXGLK3kYEMjHDJfVOvfF4Z9tBaldgM s2mfL/L5v7nW3wna6CrPg== X-UI-Out-Filterresults: notjunk:1;V01:K0:pvDmbWpjyeI=:E+vUSRyQehBK+QHYtaB9M7 Id1pfEKvOJRemYN9Q1fJeq2rGTyNCOpUGbQrzHc0F9c1Ewu7zC3qKQf2gZLqkUyb1AzE/ce5J 2AHx3O+RPfS7ArFmdPqSWATQCxGePpZRUxMc1dMgAdvA93HGlmi5v0tz0I4vrQUHsTbiLqX1q caCyK2o0TsseWWkCK5WP7IU7WwBy4YQN5zdVPtvmGhZQAdRQiESvJaWTP1s9mTBtra2SoekxW 6LaeAr5N08KdkMqTevc1A4v0ZRPSiSvqVQPjxXJ0rWCopZqOE+sPxh2XKxE+ni0Nx8fhqEBWh rkH5qxPUlB29KoAlzC9oi0E9aJgTSGMCCA4yZ5ci8Hpu1MjWH5Np/5KVtS2bJYdbTaGY84nU7 F/YyoQG7nJOp10REOSlcZ7DiJfa2BSdBrV4byfMBXVp7xiTjRQtg63SRaWqjVRaSh6tnp44an DIKKOLxUTnuGjInttdGhPfk5qJpBGU9frUx+uljiFVIg+TnbFPxr8pIxc5rh7xw4xBLj44lL6 mj4yd74VcSEzAgHixW1/GJzXkOogGz2BmmskTkHSEdn9h9jR6hh4d78dayU8yPc8O+8xAqpB4 0ebvZuBAK/KT1okEnhARYCfNMf0yxlp0WHWLoGE433xRTHjzyJGYBSDdhAiSmku8nRDS8KuFH RvXMaQ9tDffE9ggZtXicJhD32wDIUfoe0UjwjTSoc/L6pIExU1roG25tHoLrZlx/6403f6sua /x2v77DxsZs/rfxJ7vjPYC2T2jbSLV+4vkeb0wtuXf+l+W7F4e0MhbptMkHlgU9AoaMizOxk X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] X-Received-From: 208.118.235.43 X-BeenThere: bug-gnu-emacs@gnu.org List-Id: "Bug reports for GNU Emacs, the Swiss army knife of text editors" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Original-Sender: "bug-gnu-emacs" Xref: news.gmane.org gmane.emacs.bugs:132444 Archived-At: Damien Cassou 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.