1

是否可以非破坏性地将新的键值对添加到 Common Lisp (SBCL) 哈希表中？向哈希表添加新元素的标准方法是调用：

(setf (gethash key *hash-table*) value)

但是对setf修改的调用会*hash-table*破坏原始文件。我有一个应用程序，我想利用哈希表查找的效率，但我也想非破坏性地修改它们。我看到的解决方法是在对其进行操作之前复制原始哈希表，但这在我的情况下是不切实际的，因为我正在处理的哈希表包含数千个元素并复制大型哈希表，例如循环将首先否定使用它们的计算效率优势。

4

2 回答 2

5

根据您的需要，您可以只使用关联列表、使用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 提供纯粹的函数式数据结构，例如映射，它们是不可变的哈希表。它们被实现为平衡树，这比简单的方法要好。还有其他更有效的数据结构，但您可能需要自己实现它们（哈希数组映射特里（编辑：参见https://github.com/danshapero/cl-hamt，感谢@Flux））。话虽如此，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) |})
于 2020-10-17T13:51:03.727 回答
0

我不认为您可以通过引用将哈希表传递给普通 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 ,key ,(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.
于 2020-10-17T08:41:42.213 回答