parallel-processing - 键的替代哈希表相等性测试

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 key ？我也在加载 lparallel库，但在这种情况下以某种方式并行化函数是否有意义？

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

Answer 1

除了低级优化之外，它还取决于哈希表的大小和键值的可能范围。

如果键范围不比大小小多少，则使用向量而不是哈希表可能会更快。如果大小很小(小于大约 20-50)，但范围很大(例如 UUID)，也许 alist 更适合。

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

如果您的问题在某个维度上足够大，值得开销，那么并行化可能是有意义的:例如，独立比较的频率非常高，或者每个哈希表的键数非常大。

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

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