从存在于另一个数组中的数组中获取所有相同元素的最快方法

Question

我需要一种更快的方法从另一个数组中存在的数组中获取所有相同的元素。

我有两个带有 Date 对象（> 100k 元素）的非常大的数组（A 和 B）。数组 B 包含数组 A 中元素的子集。我需要过滤数组 A 中包含在数组 B 中的元素。那么，为什么不直接使用数组 B？我需要保留来自数组 A 的引用。

目前我正在使用此代码：

const A = [];
const B = [];

const result = A.filter((s) => {
     return B.indexOf(s) !== -1;
});

这种方式相当缓慢。使用我的阵列执行该操作需要超过 2 分钟。

Answer 1

先把B数组变成Set。Set#has是O(1)，但Array#indexOf/Array#includes是O(n)：

const bSet = new Set(B);
const result = A.filter(item => bSet.has(item));

这将大大提高性能。您可能可以通过使用for循环而不是来使其更快一点filter，但改进可能很小。

当两个数组都包含基元或包含对相同对象的引用时，这会起作用。如果对象是不同的，既不.indexOf也不.has也.includes将工作，在这种情况下，策略会以某种方式序列化所有的B到组原语的对象，然后再进行同样的操作，当迭代一个，看它是否随机配备在 B。