在JavaScript中可以实现数组减法的最快数量级是多少

What is the fastest order of magnitude that array subtraction can be implemented in JavaScript?

本文关键字：数量级 多少 JavaScript 数组 实现      更新时间：2023-09-26

我想要一个减法函数，它将使用两个数组，并返回数组1中不在数组2中的所有元素。

在js中实现这一点最快的是什么？是o（n）吗？

另一个选择，更快的O（n）时间，但双倍的内存（仍然是线性的），是创建自己的hashmap实现。

创建一个散列函数。对一个数组执行循环并对所有元素进行散列。将（hash，object）对存储在另一个数组中，称之为hash数组。现在循环遍历数组2，并对每个元素进行散列。让hash是hash数组中的位置，这样您就可以看到是否发生了冲突。如果您有冲突，请检查哈希数组中的对象是否与当前数组（您正在循环）中的对象相同。

这里有一个哈希表实现（使用javascript对象作为哈希），它的数组比使用indexOf()的暴力查找快100多倍（在Chrome中）。

function subtract3(one, two) {
    var hash = {}, result = [], i, len;
    // fill hash with members of second array for easy lookup
    for (i = 0, len = two.length; i < len; i++) {
        hash[two[i]] = true;
    }
    // cycle through first array and find ones that are not in two
    for (i = 0, len = one.length; i < len; i++) {
        if (!(one[i] in hash)) {
            result.push(one[i]);
        }
    }
    return(result);
}

下面是一个jsperf测试，将此选项与其他几个选项进行比较：http://jsperf.com/array-subtraction

除非您想将数组限制为可以序列化为字符串的对象，否则无法为O（n）通用地解决此问题

function substract(one, two) {
    var result = []
    for (var i = 0, len = one.length; i < len; i++) {
        var value = one[i]
        if (two.indexOf(value) === -1) {
            result.push(value)
        }
    }
    return result
}

或者如果你想使用数组迭代器

function substract(one, two) {
    return one.filter(function (value) {
        return two.indexOf(value) === -1
    })
}
相关文章：