如何在Common Lisp中重用gethash查找？

Question

我有一个哈希表,其中键是相当复杂的列表,带有符号和整数的子列表,并且应根据已存在的值修改该值.该表是使用:test #'equal.

我做了很多类似的事情:

(defun try-add (i)
  (let ((old-i (gethash complex-list table nil)))
    (if (may-add old-i)
      (push i (gethash complex-list table)))))

分析表明equal测试需要花费大量时间.我有一个优化的想法,gethash查找量可以从两个减少到一个.它可以通过重用迭代器在C++中完成,但不确定如何在Lisp中完成.有任何想法吗？

Answer 1

不要做任何特别的事情,因为实现是为你做的.

当然,这种方法是特定于实现的,并且哈希表性能在实现之间有所不同.(但随后优化问题始终是特定于实现的.)

以下答案适用于SBCL.我建议检查你的Lisp哈希表是否执行相同的优化.如果他们不这样做,请向您的供应商投诉!

在SBCL中发生的是哈希表缓存 GETHASH访问的最后一个表索引.

当调用PUTHASH(或等效地,(SETF GETHASH))时,它首先检查该缓存索引处的密钥是否是您传入的密钥的EQ.

如果是这样,则绕过整个哈希表查找例程,并且PUTHASH直接存储在缓存的索引处.

请注意,EQ只是一个指针比较,因此非常快 - 它根本不必遍历列表.

所以在你的代码示例中,根本没有开销.