如何在Common Lisp中重用gethash查找? [英] How can I reuse a gethash lookup in Common Lisp?

问题描述

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

I have a hash table where the keys are rather complex lists, with sublists of symbols and integers, and the value should be modified depending on the already existing value. The table is created with :test #'equal.

我做了很多类似的事情:

I do something similar to this a lot:

(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中完成此操作.有什么想法吗?

Profiling shows that equal tests take a lot of time. I have an optimization idea, that the amount of gethash lookups could be reduced from two to one. It can be done in C++ by reusing the iterator, but not sure how this would be done in Lisp. Any ideas?

推荐答案

不要做任何特殊的事情，因为实现会为您完成.

Don't do anything special, because the implementation does it for you.

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

Of course, this approach is implementation-specific, and hash table performance varies between implementations. (But then optimization questions are always implementation-specific.)

以下答案适用于SBCL.我建议检查您的Lisp哈希表是否执行相同的优化.如果不满意，请向您的供应商投诉！

The following answer is for SBCL. I recommend checking whether your Lisp's hash tables perform the same optimization. Complain to your vendor if they don't!

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

What happens in SBCL is that the hash table caches the last table index accessed by GETHASH.

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

When PUTHASH (or equivalently, (SETF GETHASH)) is called, it first checks whether the key at that cached index is EQ to the key that you are passing in.

如果是这样，将绕过整个哈希表查找例程，而PUTHASH将直接存储在缓存的索引中.

If so, the entire hash table lookup routine is by-passed, and PUTHASH stores directly at the cached index.

请注意，EQ只是一个指针比较，因此非常快-完全不必遍历列表.

Note that EQ is just a pointer comparison and hence extremely fast -- it does not have to traverse the list at all.

因此在您的代码示例中，根本没有开销.

So in your code example, the is no overhead at all.

这篇关于如何在Common Lisp中重用gethash查找?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！