javascript - 去除 JavaScript 列表中重复项的最佳方法是什么？

Question

我写了几个方法来将项目添加到数组中，如果它们已经在数组中，它们将被忽略。在对数据结构做了一些研究之后，我意识到我可以通过简单地将它们放在一个集合中来摆脱重复(特别是因为我不关心对象的顺序)。然而，在玩过 JavaScript 之后，我注意到相同的对象被添加到一个集合中，例如:

var mySet = new Set();
mySet.add({a:23})
console.log(mySet);
mySet.add({b:14})
console.log(mySet);
mySet.add({a:23})
console.log(mySet);

输出:

Set {Object {a: 23}}
Set {Object {a: 23}, Object {b: 14}}
Set {Object {a: 23}, Object {b: 14}, Object {a: 23}}

在这个例子中，我添加了 key->a 和 value->23 的对象，然后是另一个具有完全不同的键、值集的对象，然后又是原来的对象。我希望我的集合中只有 a->23 和 b->14。

去除列表中重复项的最佳方法是什么？

Answer 1

这些对象虽然具有相同的结构，但却是截然不同的。每个都代表内存中的一个单独空间，并且是对该内存的唯一引用。

console.log(
  { a: 23 } === { a: 23 } // false
);

这就是将同一个对象添加到集合中两次而第二次添加将被忽略的方式。

var obj = { a: 23 };
var s = new Set();

// first addition
s.add(obj);
console.log(
  ...s.values()
);

// second addition of the same object is ignored
s.add(obj);
console.log(
  ...s.values()
);

如果您想支持基于对象包含的数据而不是引用相等性来比较对象的用例，您可能需要研究的是 deep object comparison .

例如，这是利用 deep-equal 的一种方法在添加对象之前检查对象是否存在于数组中的库:

!function(e){if("object"==typeof exports&&"undefined"!=typeof module)module.exports=e();else if("function"==typeof define&&define.amd)define([],e);else{var t;t="undefined"!=typeof window?window:"undefined"!=typeof global?global:"undefined"!=typeof self?self:this,t.deepEqual=e()}}(function(){return function e(t,r,n){function o(u,i){if(!r[u]){if(!t[u]){var c="function"==typeof require&&require;if(!i&&c)return c(u,!0);if(f)return f(u,!0);var p=new Error("Cannot find module '"+u+"'");throw p.code="MODULE_NOT_FOUND",p}var l=r[u]={exports:{}};t[u][0].call(l.exports,function(e){var r=t[u][1][e];return o(r?r:e)},l,l.exports,e,t,r,n)}return r[u].exports}for(var f="function"==typeof require&&require,u=0;u<n.length;u++)o(n[u]);return o}({1:[function(e,t,r){function n(e){return null===e||void 0===e}function o(e){return!(!e||"object"!=typeof e||"number"!=typeof e.length)&&("function"==typeof e.copy&&"function"==typeof e.slice&&!(e.length>0&&"number"!=typeof e[0]))}function f(e,t,r){var f,l;if(n(e)||n(t))return!1;if(e.prototype!==t.prototype)return!1;if(c(e))return!!c(t)&&(e=u.call(e),t=u.call(t),p(e,t,r));if(o(e)){if(!o(t))return!1;if(e.length!==t.length)return!1;for(f=0;f<e.length;f++)if(e[f]!==t[f])return!1;return!0}try{var s=i(e),a=i(t)}catch(e){return!1}if(s.length!=a.length)return!1;for(s.sort(),a.sort(),f=s.length-1;f>=0;f--)if(s[f]!=a[f])return!1;for(f=s.length-1;f>=0;f--)if(l=s[f],!p(e[l],t[l],r))return!1;return typeof e==typeof t}var u=Array.prototype.slice,i=e("./lib/keys.js"),c=e("./lib/is_arguments.js"),p=t.exports=function(e,t,r){return r||(r={}),e===t||(e instanceof Date&&t instanceof Date?e.getTime()===t.getTime():!e||!t||"object"!=typeof e&&"object"!=typeof t?r.strict?e===t:e==t:f(e,t,r))}},{"./lib/is_arguments.js":2,"./lib/keys.js":3}],2:[function(e,t,r){function n(e){return"[object Arguments]"==Object.prototype.toString.call(e)}function o(e){return e&&"object"==typeof e&&"number"==typeof e.length&&Object.prototype.hasOwnProperty.call(e,"callee")&&!Object.prototype.propertyIsEnumerable.call(e,"callee")||!1}var f="[object Arguments]"==function(){return Object.prototype.toString.call(arguments)}();r=t.exports=f?n:o,r.supported=n,r.unsupported=o},{}],3:[function(e,t,r){function n(e){var t=[];for(var r in e)t.push(r);return t}r=t.exports="function"==typeof Object.keys?Object.keys:n,r.shim=n},{}]},{},[1])(1)});

function addToSet(s, value) {
  for (const curr of s.values()) {
    if (deepEqual(curr, value)) {
      return;
    }
  }
  s.add(value);
}

var mySet = new Set();

// first addition works
addToSet(mySet, {a:23});
console.log(...mySet.values());

// second addition works
addToSet(mySet, {b:14});
console.log(...mySet.values());

// addition of an object of the same structure is ignored
addToSet(mySet, {a:23});
console.log(...mySet.values());

在这种情况下，需要重点考虑的是 deepEqual 函数的时间/空间复杂度。使用这种方法，将元素添加到集合的时间复杂度从线性增加到至少二次方，即 O(setSize * numberOfPropsInLargestObject)。由于大多数版本的深度对象比较方法都是以递归方式编写的，假设它不是现代环境中的尾递归函数，这也会将空间复杂度从常量增加到线性。