我正在寻找一种高效的方法来确定两个数组是否包含相同数量的相等元素（按==的意义），任意顺序：
foo = {/*some object*/}
bar = {/*some other object*/}
a = [1,2,foo,2,bar,2]
b = [bar,2,2,2,foo,1]
sameElements(a, b) --> true
PS. 请注意，线程中几乎每个解决方案都使用 === 而不是 == 进行比较。对于我的需求来说，这样做就可以了。
比较数组作为多重集合
9
- georg
9
8个回答
7
更新5 我发布了一个新的答案，采取不同的方法。
更新
我扩展了代码，可以通过引用或等式检查。
只需将第二个参数传递为true，即可进行引用检查。
我还将示例添加到Brunos JSPerf中。
- 它以大约11次操作/秒运行进行引用检查
我会在有空闲时间解释一下代码，但是目前没有时间，抱歉。已完成
更新2。
正如Bruno在评论中指出的那样，sameElements([NaN],[NaN])会产生false。
我认为这是正确的行为，因为NaN是模棱两可的，应该总是导致false结果，至少在比较NaN.equals(NaN)时应该如此。但他说得很有道理。
无论
[1,2,foo,bar,NaN,3]是否应等于[1,3,foo,NaN,bar,2]。
好吧... 老实说，我有点犹豫它应该还是不应该，所以我添加了两个标志。
- Number.prototype.equal.NaN
- 如果为true
NaN.equals(NaN) //true
- 如果为true
- Array.prototype.equal.NaN
- 如果为true
[NaN].equals([NaN],true) //true- 请注意，这仅用于引用检查。因为深度检查将无论如何调用
Number.prototype.equals
- 如果为true
更新3：
天哪，我在排序函数中完全错过了2行。
已添加
r[0] = a._srt; //DANG i totally missed this line
r[1] = b._srt; //And this.
在Fiddle中的第105行。
这很重要，因为它确定元素的一致顺序。
更新4
我尝试优化排序函数，并成功将其提高到每秒约20个操作。
下面是更新后的代码以及更新后的fiddle =）
我选择在sort函数之外标记对象，似乎不再产生性能差异，更易读。
以下是一种方法，使用Object.defineProperty将equals函数添加到Array,Object,Number,String,Boolean's prototype，以避免出于性能原因在一个函数中进行类型检查。由于我们可以在任何元素上递归调用.equals。
但是，当然，在大型对象中检查相等性可能会导致性能问题。
因此，如果有人感到不舒服操纵本机原型，则仅进行类型检查并将其放入一个函数中
Object.defineProperty(Boolean.prototype, "equals", {
enumerable: false,
configurable: true,
value: function (c) {
return this == c; //For booleans simply return the equality
}
});
Object.defineProperty(Number.prototype, "equals", {
enumerable: false,
configurable: true,
value: function (c) {
if (Number.prototype.equals.NaN == true && isNaN(this) && c != c) return true; //let NaN equals NaN if flag set
return this == c; // else do a normal compare
}
});
Number.prototype.equals.NaN = false; //Set to true to return true for NaN == NaN
Object.defineProperty(String.prototype, "equals", {
enumerable: false,
configurable: true,
value: Boolean.prototype.equals //the same (now we covered the primitives)
});
Object.defineProperty(Object.prototype, "equals", {
enumerable: false,
configurable: true,
value: function (c, reference) {
if (true === reference) //If its a check by reference
return this === c; //return the result of comparing the reference
if (typeof this != typeof c) {
return false; //if the types don't match (Object equals primitive) immediately return
}
var d = [Object.keys(this), Object.keys(c)],//create an array with the keys of the objects, which get compared
f = d[0].length; //store length of keys of the first obj (we need it later)
if (f !== d[1].length) {//If the Objects differ in the length of their keys
return false; //immediately return
}
for (var e = 0; e < f; e++) { //iterate over the keys of the first object
if (d[0][e] != d[1][e] || !this[d[0][e]].equals(c[d[1][e]])) {
return false; //if either the key name does not match or the value does not match, return false. a call of .equal on 2 primitives simply compares them as e.g Number.prototype.equal gets called
}
}
return true; //everything is equal, return true
}
});
Object.defineProperty(Array.prototype, "equals", {
enumerable: false,
configurable: true,
value: function (c,reference) {
var d = this.length;
if (d != c.length) {
return false;
}
var f = Array.prototype.equals.sort(this.concat());
c = Array.prototype.equals.sort(c.concat(),f)
if (reference){
for (var e = 0; e < d; e++) {
if (f[e] != c[e] && !(Array.prototype.equals.NaN && f[e] != f[e] && c[e] != c[e])) {
return false;
}
}
} else {
for (var e = 0; e < d; e++) {
if (!f[e].equals(c[e])) {
return false;
}
}
}
return true;
}
});
Array.prototype.equals.NaN = false; //Set to true to allow [NaN].equals([NaN]) //true
Object.defineProperty(Array.prototype.equals,"sort",{
enumerable:false,
value:function sort (curr,prev) {
var weight = {
"[object Undefined]":6,
"[object Object]":5,
"[object Null]":4,
"[object String]":3,
"[object Number]":2,
"[object Boolean]":1
}
if (prev) { //mark the objects
for (var i = prev.length,j,t;i>0;i--) {
t = typeof (j = prev[i]);
if (j != null && t === "object") {
j._pos = i;
} else if (t !== "object" && t != "undefined" ) break;
}
}
curr.sort (sorter);
if (prev) {
for (var k = prev.length,l,t;k>0;k--) {
t = typeof (l = prev[k]);
if (t === "object" && l != null) {
delete l._pos;
} else if (t !== "object" && t != "undefined" ) break;
}
}
return curr;
function sorter (a,b) {
var tStr = Object.prototype.toString
var types = [tStr.call(a),tStr.call(b)]
var ret = [0,0];
if (types[0] === types[1] && types[0] === "[object Object]") {
if (prev) return a._pos - b._pos
else {
return a === b ? 0 : 1;
}
} else if (types [0] !== types [1]){
return weight[types[0]] - weight[types[1]]
}
return a>b?1:a<b?-1:0;
}
}
});
通过这样做，我们可以将sameElements函数简化为：
function sameElements(c, d,referenceCheck) {
return c.equals(d,referenceCheck); //call .equals of Array.prototype.
}
sameElements函数中，但需要付出类型检查的代价。
现在这里有三个例子：一个使用深度检查，两个使用引用检查。
var foo = {
a: 1,
obj: {
number: 2,
bool: true,
string: "asd"
},
arr: [1, 2, 3]
};
var bar = {
a: 1,
obj: {
number: 2,
bool: true,
string: "asd"
},
arr: [1, 2, 3]
};
var foobar = {
a: 1,
obj: {
number: 2,
bool: true,
string: "asd"
},
arr: [1, 2, 3, 4]
};
var a = [1, 2, foo, 2, bar, 2];
var b = [foo, 2, 2, 2, bar, 1];
var c = [bar, 2, 2, 2, bar, 1];
所以这些是我们要比较的数组。输出结果为：
只使用引用检查
a和b。console.log(sameElements(a,b,true)) //true 因为它们包含相同的元素只使用引用检查
b和c。console.log(sameElements(b,c,true)) //false 因为 c 包含两个 bar。深入检查
b和c。console.log(sameElements(b,c,false)) //true 因为 bar 和 foo 相等但不相同检查包含 NaN 的 2 个数组
Array.prototype.equals.NaN = true;
console.log(sameElements([NaN],[NaN],true)); //true。
Array.prototype.equals.NaN = false;
- Moritz Roessler
12
1哦...看来我误解了，只需要进行参考检查，我的错。 - Moritz Roessler
抱歉，我不太理解你的代码是做什么的。可以再多解释一点吗？ - georg
嗨 @thg435 =) 我更新了答案，现在它可以进行引用或相等性检查。并将其添加到了jsperf中。我一旦有时间就会解释它（我会在这里评论，而不是在fiddle中）。 - Moritz Roessler
@thg435 我尝试通过对代码进行注释来更好地解释。我不太擅长解释，所以如果还有任何问题，请留下评论，我会再次解释。=) - Moritz Roessler
@C5H8NNaO4
sameElements( [NaN], [NaN], true ) 返回false。 - Bruno显示剩余7条评论
2
像这样吗？
var foo = {}; var bar=[];
var a = [3,2,1,foo]; var b = [foo,1,2,3];
function comp(a,b)
{
// immediately discard if they are of different sizes
if (a.length != b.length) return false;
b = b.slice(0); // clone to keep original values after the function
a.forEach(function(e) {
var i;
if ((i = b.indexOf(e)) != -1)
b.splice(i, 1);
});
return !b.length;
}
comp(a,b);
- BrunoLM
3
1似乎可以工作，但看起来并不特别高效。切片，然后拼接...我不知道。我的数组有成千上万个项目。 - georg
需要使用切片来克隆数组。如果您不再使用它，可以删除这两行代码...实际上，您不需要克隆
a，我会更新它... - BrunoLM工作正常，但是你和Frédéric的解决方案对我的需求来说速度相当慢。 - georg
2
您可以实现以下算法：
请注意，此实现不能完全满足您的要求，因为
- 如果
a和b的长度不相同：- 返回
false。
- 返回
- 否则：
- 克隆
b， - 对于
a中的每个项：- 如果该项存在于我们克隆的
b中：- 从我们克隆的
b中删除该项，
- 从我们克隆的
- 否则：
- 返回
false。
- 返回
- 如果该项存在于我们克隆的
- 返回
true。
- 克隆
function sameElements(a, b)
{
if (a.length != b.length) {
return false;
}
var ourB = b.concat();
return a.every(function(item) {
var index = ourB.indexOf(item);
if (index < 0) {
return false;
} else {
ourB.splice(index, 1);
return true;
}
});
}
请注意，此实现不能完全满足您的要求，因为
indexOf()在内部使用严格相等(===)。如果您真的想要非严格相等(==)，则需要编写一个内部循环。- Frédéric Hamidi
5
1嗯，
sameElements([1,2],[1,2,3]) ?? - georg@thg435，没错，那个我完全忘记了。需要进行一个长度测试。我会更新我的答案。 - Frédéric Hamidi
这似乎可以工作，谢谢，但请看我的评论@BrunoLM：我的数组相当大，重复的indexOf/splice看起来不是特别高效。有更好的方法吗？ - georg
尽管相当透明，但这个版本最终却变得最慢（请参见线程中的jsperf链接）。 - georg
2
更新
正如@Bergi和@thg435指出的，我的先前实现存在缺陷，因此这里提供另一种实现：
function sameElements(a, b) {
var objs = [];
// if length is not the same then must not be equal
if (a.length != b.length) return false;
// do an initial sort which will group types
a.sort();
b.sort();
for ( var i = 0; i < a.length; i++ ) {
var aIsPrimitive = isPrimitive(a[i]);
var bIsPrimitive = isPrimitive(b[i]);
// NaN will not equal itself
if( a[i] !== a[i] ) {
if( b[i] === b[i] ) {
return false;
}
}
else if (aIsPrimitive && bIsPrimitive) {
if( a[i] != b[i] ) return false;
}
// if not primitive increment the __count property
else if (!aIsPrimitive && !bIsPrimitive) {
incrementCountA(a[i]);
incrementCountB(b[i]);
// keep track on non-primitive objects
objs.push(i);
}
// if both types are not the same then this array
// contains different number of primitives
else {
return false;
}
}
var result = true;
for (var i = 0; i < objs.length; i++) {
var ind = objs[i];
// if __aCount and __bCount match then object exists same
// number of times in both arrays
if( a[ind].__aCount !== a[ind].__bCount ) result = false;
if( b[ind].__aCount !== b[ind].__bCount ) result = false;
// revert object to what it was
// before entering this function
delete a[ind].__aCount;
delete a[ind].__bCount;
delete b[ind].__aCount;
delete b[ind].__bCount;
}
return result;
}
// inspired by @Bergi's code
function isPrimitive(arg) {
return Object(arg) !== arg;
}
function incrementCountA(arg) {
if (arg.hasOwnProperty("__aCount")) {
arg.__aCount = arg.__aCount + 1;
} else {
Object.defineProperty(arg, "__aCount", {
enumerable: false,
value: 1,
writable: true,
configurable: true
});
}
}
function incrementCountB(arg) {
if (arg.hasOwnProperty("__bCount")) {
arg.__bCount = arg.__bCount + 1;
} else {
Object.defineProperty(arg, "__bCount", {
enumerable: false,
value: 1,
writable: true,
configurable: true
});
}
}
那么只需调用该函数即可。
sameElements( ["NaN"], [NaN] ); // false
// As "1" == 1 returns true
sameElements( [1],["1"] ); // true
sameElements( [1,2], [1,2,3] ); //false
上述实现实际上定义了一个名为“__count”的新属性，用于跟踪数组中的非基元素。在函数返回之前，这些元素被删除，以使数组元素保持不变。
这里是Fiddle链接：http://jsfiddle.net/bruno/rz3Vn/14/
这里是jsperf链接：http://jsperf.com/array-comparison-1/11
我更改jsperf测试用例的原因是，正如@Bergi所说，测试数组，特别是整个数组中只有2个唯一对象的事实，并不代表我们要测试的内容。
此实现的另一个优点是，如果您需要使其与IE9之前的浏览器兼容，而不是使用defineProperty创建一个不可枚举属性，则可以使用普通属性。
- Bruno
8
虽然排序是一个好主意，但在
sameElements([bar,bar,foo], [bar,foo,foo]) 上会失败。 - Bergi@Bergi 它确实成功了。原因是尽管元素已经排序，但对于任何不是基元的元素（在这种情况下foo和bar不是），该函数使用
Array.indexOf方法来检查元素是否存在于两个数组中。请查看fiddle。 - Bruno但它应该返回
false... - Bergi这个版本确实不能正常工作，但 jsperf 链接显示了你的更多版本 - 考虑在这里重新发布它们。 - georg
显示剩余3条评论
1
我不确定"==="是否可行，问题有点模糊...
如果可以的话，这比其他可能的方法要快得多而且更简单：
function isSame(a,b){
return a.length==b.length &&
a.filter(function(a){ return b.indexOf(a)!==-1 }).length == b.length;
}
- dandavis
1
编辑2
1）感谢user2357112指出了Object.prototype.toString.call问题，这也表明了它之所以快的原因是没有考虑到数组...
我已经修复了代码，现在应该可以工作了：），不幸的是，在chrome上大约为59ops/s，在ff上为45ops/s。
Fiddle和JSPerf已更新。
编辑
1）
我修复了代码，现在支持多个变量引用相同的对象。
比以前慢了一点，但在chrome上仍然超过100ops/s。
2) 我尝试使用位掩码代替数组来保留对象的多个位置，但速度减缓了近15ops/s。
3) 如评论中所指出的，我忘记在调用[[get]]后重置tmp，已修复代码、 fiddle和perf。
感谢user2357112提供的Answer，这里介绍另一种使用计数的方法。
var sameElements = (function () {
var f, of, objectFlagName;
of = objectFlagName = "__pos";
var tstr = function (o) {
var t = typeof o;
if (o === null)
t = "null";
return t
};
var types = {};
(function () {
var tmp = {};
Object.defineProperty(types, tstr(1), {
set: function (v) {
if (f)
tmp[v] = -~tmp[v];
else
tmp[v] = ~-tmp[v];
},
get: function () {
var ret = 1;
for (var k in tmp) {
ret &= !tmp[k];
}
tmp = {};
return ret;
}
});
})();
(function () {
var tmp = {};
Object.defineProperty(types, tstr(""), {
set: function (v) {
if (f) {
tmp[v] = -~tmp[v];
} else {
tmp[v] = ~-tmp[v];
}
},
get: function () {
var ret = 1;
for (var k in tmp) {
ret &= !tmp[k];
}
tmp = {};
return ret;
}
});
})();
(function () {
var tmp = [];
function add (v) {
tmp.push(v);
if (v[of]===undefined) {
v[of] = [tmp.length -1];
} else {
v[of].push(tmp.length -1)
}
}
Object.defineProperty(types, tstr({}), {
get: function () {
var ret = true;
for (var i = tmp.length - 1; i >= 0; i--) {
var c = tmp[i]
if (typeof c !== "undefined") {
ret = false
delete c[of]
}
}
tmp = [];
return ret;
},
set: function (v) {
var pos;
if (f) {
add (v);
} else if (!f && (pos = v[of]) !== void 0) {
tmp[pos.pop()] = undefined;
if (pos.length === 0)
delete v[of];
} else {
add (v);
}
}
});
}());
(function () {
var tmp = 0;
Object.defineProperty(types, tstr(undefined), {
get: function () {
var ret = !tmp;
tmp = 0;
return ret;
},
set: function () {
tmp += f ? 1 : -1;
}
});
})();
(function () {
var tmp = 0;
Object.defineProperty(types, tstr(null), {
get: function () {
var ret = !tmp;
tmp = 0;
return ret;
},
set: function () {
tmp += f ? 1 : -1;
}
});
})();
var tIt = [tstr(1), tstr(""), tstr({}), tstr(undefined), tstr(null)];
return function eq(a, b) {
f = true;
for (var i = a.length - 1; i >= 0; i--) {
var v = a[i];
types[tstr(v)] = v;
}
f = false;
for (var k = b.length - 1; k >= 0; k--) {
var w = b[k];
types[tstr(w)] = w;
}
var r = 1;
for (var l = 0, j; j = tIt[l]; l++) {
r &= types [j]
}
return !!r;
}
})()
这里有一个JSFiddle和一个JSPerf（它使用与之前答案性能相同的数组a和b），与Closure compiled代码进行比较。
这是输出结果。注意：它不再支持深度比较。
var foo = {a:2}
var bar = {a:1};
var a = [1, 2, foo, 2, bar, 2];
var b = [foo, 2, 2, 2, bar, 1];
var c = [bar, 2, 2, 2, bar, 1];
console.log(sameElements([NaN],[NaN])); //true
console.log (sameElements ( a,b)) //true
console.log (sameElements (b,c)) //false
- Moritz Roessler
7
我目前在使用移动设备，但我注意到在对象类型的Setter中，为了支持引用相同对象的变量，我应该将“__pos”变量更改为数组，我将相应地更新答案。 - Moritz Roessler
在我的机器上，
Object.prototype.toString.call(window) === "[object global]"。我认为使用它不是一个好主意。请参考https://dev59.com/flLTa4cB1Zd3GeqPWgMI#4222755。 - user23571121另外，如果你需要调用这个函数两次呢？在第一次调用时返回 false 的情况下，所有的数据结构都会永久性地混乱。 - user2357112
1一定有更简洁的编码方式。这段代码只有它的母亲会喜欢。请重构它 :) - Gili
显示剩余2条评论
1
感谢大家分享想法！我想到了以下内容。
function sameElements(a, b) {
var hash = function(x) {
return typeof x + (typeof x == "object" ? a.indexOf(x) : x);
}
return a.map(hash).sort().join() == b.map(hash).sort().join();
}
这不是最快的解决方案，但在我看来，是迄今为止最易读的方案。
- georg
0
使用高效的查找表来计算元素的数量：
function sameElements(a) { // can compare any number of arrays
var map, maps = [], // counting booleans, numbers and strings
nulls = [], // counting undefined and null
nans = [], // counting nans
objs, counts, objects = [],
al = arguments.length;
// quick escapes:
if (al < 2)
return true;
var l0 = a.length;
if ([].slice.call(arguments).some(function(s) { return s.length != l0; }))
return false;
for (var i=0; i<al; i++) {
var multiset = arguments[i];
maps.push(map = {}); // better: Object.create(null);
objects.push({vals: objs=[], count: counts=[]});
nulls[i] = 0;
nans[i] = 0;
for (var j=0; j<l0; j++) {
var val = multiset[j];
if (val !== val)
nans[i]++;
else if (val === null)
nulls[i]++;
else if (Object(val) === val) { // non-primitive
var ind = objs.indexOf(val);
if (ind > -1)
counts[ind]++;
else
objs.push(val), counts.push(1);
} else { // booleans, strings and numbers do compare together
if (typeof val == "boolean")
val = +val;
if (val in map)
map[val]++;
else
map[val] = 1;
}
}
}
// testing if nulls and nans are the same everywhere
for (var i=1; i<al; i++)
if (nulls[i] != nulls[0] || nans[i] != nans[0])
return false;
// testing if primitives were the same everywhere
var map0 = maps[0];
for (var el in map0)
for (var i=1; i<al; i++) {
if (map0[el] !== maps[i][el])
return false;
delete maps[i][el];
}
for (var i=1; i<al; i++)
for (var el in maps[i])
return false;
// testing if objects were the same everywhere
var objs0 = objects[0].vals,
ol = objs0.length;
counts0 = objects[0].count;
for (var i=1; i<al; i++)
if (objects[i].count.length != ol)
return false;
for (var i=0; i<ol; i++)
for (var j=1; j<al; j++)
if (objects[j].count[ objects[j].vals.indexOf(objs0[i]) ] != counts0[i])
return false;
// else, the multisets are equal:
return true;
}
这个方法仍然使用indexOf在所有对象中进行搜索，因此如果您有包含许多不同对象的多重集合，您可能还需要优化该部分。查看唯一ID或对象签名（以及它的重复问题）以了解如何为它们获取查找表键。而且，如果您的多重集合中没有太多的原始值，您可能只需将它们存储在数组中，并在比较每个项目之前对其进行排序（就像@Bruno所做的那样）。
免责声明：此解决方案不会尝试获取对象的[[PrimitiveValue]]，因为它们永远不会被视为等于基元值（而==会这样做）。
这里是@Bruno jsperf测试答案的更新，但我想只有两个对象（每个对象在10k数组中出现500次）和没有重复的原始值并不能代表全部情况。
- Bergi
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
foo和bar在==的意义上永远不会相等，或者你想比较对象元素的属性（深入比较）吗？ - Mattfoo和bar不必相等。数组包含foo和bar两个对象。我想这就是重点（顺便说一下，我之前也感到困惑）。 - Felix KlingSet或Map（带有实例数量）来代替数组 :-) - Bergi