密钥的替代哈希表相等性测试

Question

SBCL分析显示我的一个Common Lisp哈希表函数耗费了大量时间.该函数比较两个哈希表以确定它们是否具有相同的键:

(defun same-keys (ht1 ht2)
  "Returns t if two hash tables have the same keys."
  (declare (hash-table ht1 ht2))
  (when (= (hash-table-count ht1) (hash-table-count ht2))
    (maphash (lambda (ht1-key ht1-value)
               (declare (ignore ht1-value))
               (unless (gethash ht1-key ht2)
                 (return-from same-keys nil)))
             ht1)
    t))

有没有办法加速这个,因为哈希表总是#'eql带fixnum键？我也在加载lparallel库,但在这种情况下以某种方式并行化函数是否有意义？

编辑:哈希表的大小可以是大约10到100个条目.ht键范围从100扩展到999,999,999,999,但在此范围内实际使用的总可能的fixnums是稀疏的.每个ht值都是t或列表.所有哈希表的键值关联都在加载时设置.通过复制现有哈希表并逐步添加或删除条目,在运行时创建新哈希表.常规哈希表的读取,写入和复制似乎不是问题.

Answer 1

除了低级优化之外,它还取决于哈希表的大小以及键的可能值范围.

如果键范围不小于大小,则使用向量而不是散列表可能会更快.如果尺寸较小(小于约20-50),但范围较大(例如UUID),则alists可能更适合.

如果写入这些哈希表不是瓶颈,那么您可以使用包含一些辅助数据结构的对象来包装哈希表以进行密钥比较.这可能是一些位向量标记使用的键,或所有使用的键的完整自定义哈希,或(如果大小和范围真的很大)类似布隆过滤器.

并行化可能是有意义的,如果你的问题是,在某些方面足够大,使其价值的开销:例如,无论是独立的比较的频率非常高,或每哈希表非常大按键的数量.

一种可能的低级优化是使用loop而不是maphash,其中大部分时间可以编译为更快的代码:

(loop :for key1 :being :the :hash-keys :of ht1
      :always (nth-value 1 (gethash key1 ht2)))