vector - 为什么使用集合过滤比使用向量过滤性能更好？

Question

经过一些研究，我最近能够通过使用集合而不是向量进行比较来显着提高某些代码的性能。这是初始代码的一个简单示例:

(def target-ids ["a" "b" "c"])

(def maps-to-search-through 
  [{"id": "a" "value": "example"} 
   {"id": "e" "value": "example-2"}])

(filter (fn [i] (some #(= (:id i) %) target-ids)) maps-to-search-through)

这是优化后的代码:

(def target-ids #{"a" "b" "c"})

(def maps-to-search-through
  [{"id": "a" "value": "example"} 
   {"id": "e" "value": "example-2"}])

(filter (comp target-ids :id) maps-to-search-through)

作为引用，target-ids 和 maps-to-search-through 都是动态生成的，并且每个都可以包含数千个值——尽管 maps -to-search-through 将始终比 target-ids 至少大 5 倍。

我在网上找到的所有建议和文档都表明这种改进，特别是使用集合而不是向量，会明显更快，但没有详细说明为什么会这样。我知道在最初的情况下，filter 做了很多工作——在每一步都遍历两个向量。但我不明白为什么不是改进代码中的情况。

谁能帮忙解释一下？

Answer 1

集合是设计为仅包含唯一值的数据结构。您还可以将它们用作函数来检查给定值是否是该集合的成员 - 就​​像您使用 target-ids 集合一样。它基本上归结为在 JVM 端调用 Set.contains，它使用了一些聪明的基于哈希的逻辑。

您的第一个解决方案使用 some 遍历向量，因此它类似于嵌套的 for 循环，但显然速度较慢。