From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: "Pascal J. Bourguignon" Newsgroups: gmane.emacs.help Subject: Re: plists, alists, and hashtables Date: Fri, 07 Aug 2015 02:08:58 +0200 Organization: Informatimago Message-ID: <87h9ocm02t.fsf@kuiper.lan.informatimago.com> References: <876150vwaa.fsf@mbork.pl> <873803x5q4.fsf@kuiper.lan.informatimago.com> <87a8u7we9s.fsf_-_@lifelogs.com> <877fp8t9ru.fsf@lifelogs.com> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Trace: ger.gmane.org 1438906227 19608 80.91.229.3 (7 Aug 2015 00:10:27 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Fri, 7 Aug 2015 00:10:27 +0000 (UTC) To: help-gnu-emacs@gnu.org Original-X-From: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane.org@gnu.org Fri Aug 07 02:10:20 2015 Return-path: Envelope-to: geh-help-gnu-emacs@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1ZNVEp-0003zc-Fi for geh-help-gnu-emacs@m.gmane.org; Fri, 07 Aug 2015 02:10:19 +0200 Original-Received: from localhost ([::1]:47359 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ZNVEo-0000lr-HD for geh-help-gnu-emacs@m.gmane.org; Thu, 06 Aug 2015 20:10:18 -0400 Original-Path: usenet.stanford.edu!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail Original-Newsgroups: gnu.emacs.help Original-Lines: 136 Original-X-Trace: individual.net 12fy+SZ8MEIIhzywoLF1QgPe2zkDtPkLbpVWS05QtF1QmJfTzs Cancel-Lock: sha1:NGY0MGU3YWRjOThiZGMxMWU3MGU3ZDE0OWZiYzJkYmFhMjU3ZWQ1Mw== sha1:Ro38FbfH0CBi2A+F6s1AOLn9BiM= Face: iVBORw0KGgoAAAANSUhEUgAAADAAAAAwAQMAAABtzGvEAAAABlBMVEUAAAD///+l2Z/dAAAA oElEQVR4nK3OsRHCMAwF0O8YQufUNIQRGIAja9CxSA55AxZgFO4coMgYrEDDQZWPIlNAjwq9 033pbOBPtbXuB6PKNBn5gZkhGa86Z4x2wE67O+06WxGD/HCOGR0deY3f9Ijwwt7rNGNf6Oac l/GuZTF1wFGKiYYHKSFAkjIo1b6sCYS1sVmFhhhahKQssRjRT90ITWUk6vvK3RsPGs+M1RuR mV+hO/VvFAAAAABJRU5ErkJggg== X-Accept-Language: fr, es, en User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.3 (gnu/linux) Original-Xref: usenet.stanford.edu gnu.emacs.help:214022 X-BeenThere: help-gnu-emacs@gnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: Users list for the GNU Emacs text editor List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane.org@gnu.org Original-Sender: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.help:106307 Archived-At: Ted Zlatanov writes: > So you have to do > > (delq nil (mapcar #'car-safe '((a) (b 1) (c . 2) d))) > > When the backend implementation is also the frontend, as with alists, > you have to go through the whole alist to collect the keys. That's the > access-time looping and parsing I mean. By contrast, the hashtable > implementation (whether it does it now or not) can keep the list of keys > and update it only when the data is modified. At access time, the keys > are instantly available. Only they are NOT instantly available. First it has to compute the hash value, then it has to compute a division to find the modulo, and finally it still has to walk a list or an array when there are collisions. All this takes time, so much time that it's faster to walk 100 cons cells and perform 50 comparisons of the keys in an a-list, that doing all that in a hash-table! Benchmarks prove it! Now, I should mention that emacs lisp is an implementation where the difference is the biggest. In clisp (similar to emacs lisp, compiles to a bytecode VM), the break-even point is at 35 entries, and in other CL implementations compiling to native code, the break-even point is at 5 or 6 entries. That means that there's room to optimize hash-tables in emacs lisp. Nonetheless, there's an incompressible minimum break-even of half a dozen, and most dictionaries ARE that small. > Maybe the macro is good enough, but I think the keys and values have to > be clearly separated from each other and from other cells to make it > visually useful. I understand that, and I cannot advise more strongly that you add newlines and indent your data to clearly show it. (hash-table k1 v1 kkkk2 v2 k3 vvvvvv3) (use M-x align-cols) Notice that often keys are keywords: (hash-table :k1 v1 :kkkk2 v2 :k3 vvvvvv3) and emacs fontifies them nicely. Also, I would admit that using parentheses around the entries could help editing the data structure, since that allows adding or removing entries easily with a structural editor like emacs+paredit. (mhash-table (k1 v1) (kkkk2 v2) (k3 vvvvvv3)) It works well enough for a macro (eg. let), but for a function it is a real bother: (fhash-table '(k1 v1) (list 'kkkk2 (+ 3 4)) (list 'k3 (f 'k3))) Therefore I wouldn't advise to use anything more complex than a even number of arguments, alternating keys and values, to a function constructor. > The key for me is that I'm not looking to make > hashtables themselves more prominent, but to give ELisp users a way to > read and write maps more clearly and in a way that maps more closely to > a true map data type (which I thought the hashtable was). > > The second part of my question was whether Customize support for > hashtables would make them more approachable and useful. This could definitely help. > SM> More importantly, mathematical maps are persistent, whereas your > SM> apparently favorite implementation (the hash-table) is not persistent, > SM> contrary to (e.g.) alists. > > I am not sure what you mean. Perhaps it's a problem with the > terminology. Could you explain? SM means immutable. And indeed, contrarily to the benchmark code I presented earlier, the natural usage of a-lists is: Is a key present? (assoc key alist) ; O(n) Value for the key: (cdr (assoc key alist)) ; O(n) Add a key/value: (acons key value alist) ; O(1) Remove a key: now, if you use the "Is a key present?" above, you will need: (remove key alist :key 'car) ; O(n) otherwise (ie. when no value can be nil) you can just do: (acons key nil alist) ; O(1) The a-lists are therefore not mutated, and can be shared as the tail of several variablt a-lists. (defvar *defaults* '((:move . walk) (:eat . swallow))) (defvar *bird* (acons :move 'fly *defaults*)) (defvar *mouse* (acons :eat 'chew *defaults*)) (defvar *dead-mouse* (acons :move nil *mouse*)) (list *dead-mouse* *mouse* *bird* *defaults*) --> (((:move) . #1=((:eat . chew) . #2=((:move . walk) (:eat . swallow)))) #1# ((:move . fly) . #2#) #2#) -- __Pascal Bourguignon__ http://www.informatimago.com/ “The factory of the future will have only two employees, a man and a dog. The man will be there to feed the dog. The dog will be there to keep the man from touching the equipment.” -- Carl Bass CEO Autodesk