哈希的自定义测试 Table Common Lisp 中的相等性
Custom Test for Hash Table Equality in Common Lisp
两个散列 tables 相等性的简单测试是 (equalp ht1 ht2)，它测试 (1) 相同的 :test 参数，(2) 相同的散列-table-count ，（3）相同的键和值，以及（4）相等的值。然而，我需要一个更快的比较，因为这个简单的测试消耗了大约 40% 的程序 运行 时间（根据 sbcl 中的统计分析）。所以看起来（1）和（4）以及（3）的一部分是不必要的。以下是减少 运行 时间的尝试（包括来自 coredump 的建议改进）：
(defun hash-table-equal-keys (ht1 ht2)
"Determines if all the keys of two hash tables are the same."
(and (= (hash-table-count ht1) (hash-table-count ht2))
(loop for key1 being the hash-keys of ht1
always (gethash key1 ht2))))
不过，对运行时间的影响可以忽略不计。
基本需求只涉及table中的presence/absence个key，在运行时间被频繁访问和更新。密钥也在 运行 时间根据一些变量（例如 sym1、sym2、...）计算，这些变量的值取自一组固定的符号。目前我正在使用一个宏进行设置，其中一方面使用 (gethash (list sym1 sym2 ...) ht) 构建散列 table access/update。但这需要一个低效的 #'equal 散列 table，此外还需要密钥的构造和列表构建。
一种更有效的方法可能是让宏构建一个类似 (gethash (intern (concatenate 'string (symbol-name sym1) (symbol-name sym2) ...)) ht) 的访问，它基本上用字符串连接代替列表构建。它还允许 #'eq 散列 table。这种方法有什么问题吗？
更新：将程序更改为使用带连接的#'eq 散列table 会导致性能更差。显然，将键从列表转换为符号涉及太多开销。
第一个测试条件(= (hash-table-count ht1) (hash-table-count ht2))先遍历ht1，再遍历ht2。
根据您的评论，您有一组符号列表。比较这些（这也会发生在散列table查找中）可能会很昂贵，如果你查找的键每次都被散列。
也许你可以用一个在创建时有更多开销但比较更快的自定义结构替换哈希-table：在创建时，你将内容放入一个规范的顺序（对它们进行排序），然后对它们进行哈希处理（您很可能需要一个 good 哈希函数；sxhash 通常是针对速度而不是抗碰撞性进行了优化）。然后比较变成散列（整数）相等。
之前的澄清变成了更多的回答：
如前所述，首先创建一个散列 table 将每个可能的符号与一个整数（或 fixnum）相关联。由于符号少于 100 个，因此数字范围从 1 到 99。然后在运行时，将给定的符号序列转换为它们各自的整数：例如，(sym1 sym2 sym3) -> (16 88 3)。通过将第一个乘以 1，将第二个乘以 100，将第三个乘以 100x100=10,000，可以将它们组合成一个更大的整数，如果有更多整数，则以此类推，边走边求和。这种组合是有效的，因为它基于整数运算。生成的整数对于输入整数的任何排列应该是唯一的，并且可以在 eql 哈希中使用 table 以访问原始符号序列。
两个散列 tables 相等性的简单测试是 (equalp ht1 ht2)，它测试 (1) 相同的 :test 参数，(2) 相同的散列-table-count ，（3）相同的键和值，以及（4）相等的值。然而，我需要一个更快的比较，因为这个简单的测试消耗了大约 40% 的程序 运行 时间（根据 sbcl 中的统计分析）。所以看起来（1）和（4）以及（3）的一部分是不必要的。以下是减少 运行 时间的尝试（包括来自 coredump 的建议改进）：
(defun hash-table-equal-keys (ht1 ht2)
"Determines if all the keys of two hash tables are the same."
(and (= (hash-table-count ht1) (hash-table-count ht2))
(loop for key1 being the hash-keys of ht1
always (gethash key1 ht2))))
不过，对运行时间的影响可以忽略不计。
基本需求只涉及table中的presence/absence个key，在运行时间被频繁访问和更新。密钥也在 运行 时间根据一些变量（例如 sym1、sym2、...）计算，这些变量的值取自一组固定的符号。目前我正在使用一个宏进行设置，其中一方面使用 (gethash (list sym1 sym2 ...) ht) 构建散列 table access/update。但这需要一个低效的 #'equal 散列 table，此外还需要密钥的构造和列表构建。
一种更有效的方法可能是让宏构建一个类似 (gethash (intern (concatenate 'string (symbol-name sym1) (symbol-name sym2) ...)) ht) 的访问，它基本上用字符串连接代替列表构建。它还允许 #'eq 散列 table。这种方法有什么问题吗？
更新：将程序更改为使用带连接的#'eq 散列table 会导致性能更差。显然，将键从列表转换为符号涉及太多开销。
第一个测试条件(= (hash-table-count ht1) (hash-table-count ht2))先遍历ht1，再遍历ht2。
根据您的评论，您有一组符号列表。比较这些（这也会发生在散列table查找中）可能会很昂贵，如果你查找的键每次都被散列。
也许你可以用一个在创建时有更多开销但比较更快的自定义结构替换哈希-table：在创建时，你将内容放入一个规范的顺序（对它们进行排序），然后对它们进行哈希处理（您很可能需要一个 good 哈希函数；sxhash 通常是针对速度而不是抗碰撞性进行了优化）。然后比较变成散列（整数）相等。
之前的澄清变成了更多的回答：
如前所述，首先创建一个散列 table 将每个可能的符号与一个整数（或 fixnum）相关联。由于符号少于 100 个，因此数字范围从 1 到 99。然后在运行时，将给定的符号序列转换为它们各自的整数：例如，(sym1 sym2 sym3) -> (16 88 3)。通过将第一个乘以 1，将第二个乘以 100，将第三个乘以 100x100=10,000，可以将它们组合成一个更大的整数，如果有更多整数，则以此类推，边走边求和。这种组合是有效的，因为它基于整数运算。生成的整数对于输入整数的任何排列应该是唯一的，并且可以在 eql 哈希中使用 table 以访问原始符号序列。