具有很少字段的javascript数组比较

Question

我有两个数组(data 和 data_not_included)。这些数组的每个元素都有属性 ID 和名称。我这样填写:

data[i] = {
           name :products.models[i].get('name'),
           id :  products.models[i].get('id')
          };

现在我想显示数据中不在 data_not_included 数组中的元素。比如我有

data=[{name: Sugar}{id: 1},{name: Butter}{id: 2},{name: Cola}{id: 3}]
// and
data_nat_included = [{name: Sugar}{id: 1},{name: Butter}{id: 2}].

它应该只显示 {name: Cola}{id: 3}。

这是我已经完成的:

for(var j=0;j<data_not_icluded.length;j++)
{
    for(var i=0;i<data.length;i++)
    {
        if(data[i].id != data_not_icluded[j].id ){
          //but this doesnt work for me it displayes a lot of element many times
        }
     }
}

Answer 1

这两个答案都渐近不好。这意味着它们在次优时间运行。换句话说，它们是解决问题的幼稚方法。这个问题在数据库领域更广为人知，其中连接操作很常见。众所周知，连接的复杂度为 O(log n * n + log m * m)，其中 n 是第一个表中的元素数，m 是第二个表中元素的数量。这比其他示例 O(n^2) 中提供的简单解决方案所需的操作要少。

但是，如果对您的数据了解更多，例如，我希望这些值是唯一的并且可以轻松序列化为字符串，您甚至可以将复杂性降低到 O(n + m) 通过简单地创建要比较的对象的哈希值。方法如下:

其中 n 是第一个数组中元素的数量，m 是第二个数组中元素的数量。

var data = [{ name: "Sugar" },
            { id: 1 },
            { name: "Butter" },
            { id: 2 },
            { name: "Cola" },
            { id: 3 }];
var dataNatIncluded = [{ name: "Sugar" },
                       { id: 1 },
                       { name: "Butter" },
                       { id: 2 }];

function join(a, b) {
    var hashA = {}, hashB = {}, p, result = [];
    function setter(hash) {
        return function (element) { hash[JSON.stringify(element)] = element; };
    }
    a.forEach(setter(hashA));
    b.forEach(setter(hashB));
    for (p in hashB) delete hashA[p];
    for (p in hashA) result.push(hashA[p]);
    return result;
}
// [{ name: "Cola" }, { id: 3 }]