有没有向量的交集函数？

Question

人们经常会发现，与向量相比，列表具有性能劣势的语句，这是因为consing和额外的gc步骤，以及一些函数在接受列表和向量的通用序列上的工作。

但是像intersection这样的一些函数需要两个列表。有没有为矢量提供替代方案的库？

我从这样的东西开始，但感觉应该有一个更成熟的解决方案。

(defun vec-intersec (vec-1 vec-2 &aux (result (make-array 0 :adjustable t :fill-pointer 0)))
  "A simple implementation of intersection for vectors instead of lists."
  (loop :for v1 :across vec-1
        :if (find v1 vec-2 :test #'equal)
          :do (vector-push-extend v1 result))
  result)

Answer 1

它总是取决于你的集合的大小以及你想要用它做什么。

在大约20到50个元素以下，列表通常是完全可以的，即使是随机访问(如果你不是在一个紧密的内部循环中，或者没有太多的关注)。

如果你已经有了向量，那么对其中一个向量进行排序可能是最方便的，这样你就可以进行二进制搜索，而不是天真的线性搜索。如果这还不够，而且您的集合更大，那么将元素放入哈希表(作为键，带有适当的:test)可以提供更快的(分期)查找。

这应该会让你走得很远。如果您发现了一个无法通过这种简单方法解决的问题，那么您可能希望研究一下FSet或CL-Containers，它们支持更高级的数据结构。