键的可选哈希表相等性测试
键的可选哈希表相等性测试
提问于 2019-02-18 03:42:12
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))考虑到哈希表总是带有fixnum键的#'eql，有没有办法加快这一速度？我还加载了lparallel库，但在这种情况下，以某种方式并行化函数是否有意义？
编辑:哈希表的大小可以从大约10到100个条目。ht键的范围从100到999,999,999,999,999,999，但是在这个范围内实际使用的总可能的固定数是稀疏的。每个ht值要么是t，要么是一个列表。所有哈希表的键值关联都是在加载时设置的。新的哈希表是在运行时通过复制现有哈希表并增量地添加或删除条目来创建的。常规的哈希表读取、写入和复制似乎不是问题。
Stack Overflow用户
回答已采纳
发布于 2019-02-18 05:39:25
除了低级优化之外，它还取决于哈希表的大小和键值的可能范围。
如果键范围并不比大小小很多，那么使用向量可能比使用哈希表更快。如果大小较小(小于20-50)，但范围较大(例如UUID)，则are可能更适合。
如果写入这些哈希表不是瓶颈，那么您可以将哈希表包装为包含一些辅助数据结构的对象，以便进行键比较。这可能是标记使用的键的一些位向量，或者所有使用的键的完整的自定义散列，或者(如果大小和范围真的很大)类似于布隆过滤器的东西。
如果您的问题在某些维度上足够大，使其值得开销，那么并行化可能是有意义的:例如，要么独立比较的频率非常高，要么每个哈希表的键数量非常大。
一种可能的低级优化是使用loop而不是maphash，后者在大多数情况下可以编译成更快的代码：
(loop :for key1 :being :the :hash-keys :of ht1
:always (nth-value 1 (gethash key1 ht2)))页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/54736953
复制相关文章
相似问题
腾讯云开发者
