数组过滤-摆脱O(n^2)

Question

我需要对一个非常大（超过200k元素）的对象数组执行两个过滤操作，因此我希望我的javascript代码速度尽可能快。

第一个过滤器很简单，因为我只需要删除空元素（null）：

let validArr = originalArr.filter(el => { return el != null });

第二个过滤器是检查validArr[i].name是否等于另一个数组中的元素之一。目前我是这样做的：

for(let i = 0, l = validArr.length; i < l; i++) {
    if (findInArray(validArr[i].name, otherArr)) {
        finalArr.push({
            name: validNpc[i].nick,
            id: validNpc[i].id
        });
    }
}

const findInArray = (val, arr) => {
    for(let i = 0, l = arr.length; i < l; i++) {
        if(arr[i] === val) return true;
    }
    return false;
};

在循环中我进行了微小的优化，但存在O(n^2)的问题，我想对其进行重构，但不知道如何做。

- BT101

---

以下是有关编程的内容，请将其翻译成中文。请仅返回翻译文本：一些示例数据会很有帮助，请添加它。抱歉，您没有提供需要翻译的具体内容。如果您能提供更多信息，我将非常乐意为您进行翻译。 - Maheer Ali

validArr中的“name”属性值到底是什么？如果它们是字符串，您可以将otherArr转换为一个简单对象，其中“name”值作为属性名称，像true或1这样的值作为属性值。然后您只需进行一个简单的属性查找即可。 - Pointy

@Pointy 或者使用 Set。 - melpomene

@melpomene 是的，当然可以；我做得不多，因为在我的个人世界中，我主要使用ES5，但这将会更好。 - Pointy

小注释，.filter(el => { return el != null }) 可以简化为 .filter(el => !!el)。 - Jeremy Thille

Answer 1

将otherArr转换为Set，然后查找只需要O(1)，整个循环的时间复杂度为O(n):

  const names = new Set(otherArr);

  const result = validArr
    .filter(it => names.has(it.name))
    .map(({ nick, id }) => ({ name: nick, id }));

- Jonas Wilms

---

谢谢您，现在我想起来了，我还需要第三个过滤器。很抱歉我没有在问题中提到它，请给我一分钟，我会编辑我的问题。 - BT101

构造函数 (new Set(otherArr)) 的时间复杂度是线性的吗？我找不到相关信息。 - mbojko

@mbojko 是的，必须得这样。 - Jonas Wilms

我在jsperf上检查了set和loop，结果显示loop比较快...但只适用于元素数量低于200的数组。https://jsperf.com/loop-vs-set/1 你的示例是否确实是线性的？.has方法如何在不循环集合的情况下知道它包含值？ - BT101

@bt101 是的，时间复杂度只对较大的数据集提供了一个很好的衡量标准。正如你所说，对于200个元素或更多的情况来说会更好。在Map上的创建/插入/查找是O(1)，但这些操作仍然是昂贵的。只有当n增长时才能获得其好处。你应该阅读关于哈希表的内容。 - Jonas Wilms

Answer 2

你可以使用具有O(1)时间复杂度的Set和has方法。最初的回答中提到了这些方法。

otherArr = new Set(otherArr);
for(let i = 0, l = validArr.length; i < l; i++) {
    if (findInArray(validArr[i].name, otherArr)) {
        finalArr.push({
            name: validNpc[i].nick,
            id: validNpc[i].id
        });
    }
}

const findInArray = (val, arr) => {
    return arr.has(val)
};

你可以使用forEach()来清理你的代码。最初的回答。

otherArr = new Set(otherArr)
const finalArr = [];
validArr.forEach(x => {
    if(otherArr.has(x.name)){
       finalArr.push({ name:x.nick, id:x.id })
    }
})

- Maheer Ali

---

你并没有真正使用 reduce 来构建一个值。你只是利用它迭代数组的副作用。同样的代码可以使用 filter、map 或 forEach 来编写。 - melpomene

@melpomene 我明白你的意思了。我用 forEach 的解决方案进行了更新。 - Maheer Ali