根据您的需要,您也许可以只使用关联列表,使用assoc
和其他函数在现有绑定列表上建立新绑定。 assoc
返回第一个匹配元素的事实意味着您可以阴影绑定:
(let ((list '((:a . 1) (:b . 2))))
(acons :b 3 list))
=> ((:b . 3) (:a . 1) (:b . 2))
如果在结果列表中调用(assoc :b list)
,则条目将为(:b . 3)
,但原始列表未修改。
FSet
如果关联列表不够,则FSet库将为Common Lisp提供纯功能性的数据结构,例如映射,它们是不可变的哈希表。它们被实现为平衡树,这比幼稚的方法要好。还有其他一些数据结构更有效,但是您可能需要自己实现(Hash array mapped trie)。话虽这么说,FSet总体上足够好。
FSet可通过Quicklisp获得
USER> (ql:quickload :fset)
创建地图;请注意,如果您安装了相应的阅读器宏,则将再次读取打印的表示形式。但是您无需修改语法表就可以完美地使用该库。
USER> (fset:map (:a 0) (:b 1))
#{| (:A 0) (:B 1) |}
使用:c
的新绑定更新以前的地图:
USER> (fset:with * :c 3)
#{| (:A 0) (:B 1) (:C 3) |}
使用:b
的新绑定更新前一张地图,这会遮盖上一张:
USER> (fset:with * :b 4)
#{| (:A 0) (:B 4) (:C 3) |}
所有中间图均未修改:
USER> (list * ** *** )
(#{| (:A 0) (:B 4) (:C 3) |}
#{| (:A 0) (:B 1) (:C 3) |}
#{| (:A 0) (:B 1) |})
,
我认为您不能通过引用将哈希表传递给通用Lisp中的另一个哈希表。
但是我有一个主意是如何避免复制整个哈希表,
一次调用即可获得结果是使用默认值参数位置
的gethash
。
(gethash key ht default-value)
返回key
中不存在ht
时默认值的值。
;; prepare three example hash-tables,where *h3* and *h2* gets the additional keys
;; and if a key is not present in *h3*,one should look up in *h2*,and if not there too,in *h1*.
(defparameter *h1* (make-hash-table))
(setf (gethash 'a *h1*) 1)
(setf (gethash 'b *h1*) 2)
(setf (gethash 'c *h1*) 3)
(defparameter *h2* (make-hash-table))
(setf (gethash 'd *h2*) 4)
(setf (gethash 'e *h2*) 5)
(defparameter *h3* (make-hash-table))
(setf (gethash 'f *h3*) 6)
;; the call
(gethash 'a *h3* (gethash 'a *h2* (gethash 'a *h1*)))
;; would give the desired result `1`.
;; let us assume,there is a chain of hash-tables *hk* *h(k-1)* ... *h2* *h1*
;; in which one should look up into that order.
;; Then it is to us to build the code
;; (gethash 'a *hk* (gethash 'a *h(k-1)* ...(gethash 'a *h2* (gethash 'a *h1*))...))
;; automatically for every lookup.
;; this macro does it:
(defmacro mget (key hash-tables-list)
(flet ((inject-last (e1 e2) `(,@e1,e2)))
(reduce #'inject-last
(mapcar (lambda (ht) `(gethash,key,ht))
(nreverse hash-tables-list)))))
;; let's see its macroexpansion:
(macroexpand-1 '(mget 'a (*h3* *h2* *h1*)))
;; (GETHASH 'A *H3* (GETHASH 'A *H2* (GETHASH 'A *H1*))) ;
;; T
;; and run the code:
(mget 'a (*h2* *h1*))
;; 1 ;
;; NIL
一个人可以附加信息,这是要查找的下一个哈希表
在哈希表对象中。甚至可以自动生成列表(*h3* *h2* *h1*)
,以便仅写入
(gethash* key ht)
然后调用mget
...
当然,通过所有这些,哈希访问会变慢。
这是在复制整个哈希表或在每次调用时为性能付出代价之间的折衷...
自动查找由*h3*
扩展的哈希表
(setf (get '*h3* 'extendeds) '(*h2* *h1*))
(setf (get '*h2* 'extendeds) '(*h1*))
(defun collect-extendeds (hts)
(let ((res (loop for ht in hts
nconcing (get ht 'extendeds))))
(remove-duplicates res)))
;; this function can recursively retrieve all hashtables
(defun get-extendeds* (hts &optional (acc '()))
(let ((hts (if (listp hts) hts (list hts))))
(let ((nexts (collect-extendeds hts)))
(cond ((every #'null nexts) (nreverse (remove-duplicates (append hts acc))))
(t (get-extendeds* nexts (remove-duplicates (append hts acc))))))))
;; write a macro to retrieve key's value from all downstream hashtables
(defmacro geth (key ht)
`(mget,(get-extendeds* ht)))
(geth 'a *h3*)
;; 1 ;
;; NIL ;; NIL because it was not in *h3* directly but in one of the hashtables
;; which it extends.
;; problem is if 'NIL is a value of an existing key,;; one would still get 'NIL NIL.
本文链接:https://www.f2er.com/1381409.html