将数组作为(多)集进行比较
Compare arrays as (multi-) sets
我正在寻找一种有效的方法来找出两个数组是否包含相同数量的相等元素(在==
意义上),以任何顺序:
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
p。请注意,线程中的几乎每个解决方案都使用===
而不是==
进行比较。这对我的需求来说很好。
更新5 我用一种不同的方法发了一个新的答案。
更新我扩展了代码,使其具有通过reference
或equality
检查的可能性
传递true
作为第二个参数来做引用检查。
我还将示例添加到 bruno JSPerf
- 它以大约11 ops/s的速度运行
更新
就像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
- 如果真的
-
NaN.equals(NaN) //true
-
- 如果真的
- Array.prototype.equal.NaN
- 如果真的
-
[NaN].equals([NaN],true) //true
- 注意,这仅用于参考检查。因为深度检查无论如何都会调用
Number.prototype.equals
-
- 如果真的
当我在排序函数中完全遗漏了2行
添加 r[0] = a._srt; //DANG i totally missed this line
r[1] = b._srt; //And this.
第105行
这很重要,因为它决定了元素的一致顺序。
更新4
我试着优化一下排序函数,并设法将其提高到大约20 ops/s。
下面是更新后的代码,以及更新后的fiddle =)
我还选择在排序函数之外标记对象,它似乎不再使性能差异,而且它更具可读性
下面是使用
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
函数中,以牺牲类型检查的代价。
现在这里有3个例子:1个深度检查,2个引用检查。
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 As they contain the same elements
检查
b
和c
只引用console.log (sameElements (b,c,true)) //false as c contains bar twice.
深入检查
b
和c
console.log (sameElements (b,c,false)) //true as bar and foo are equal but not the same
检查包含NaN的2个数组
Array.prototype.equals.NaN = true;
console.log(sameElements([NaN],[NaN],true)); //true.
Array.prototype.equals.NaN = false;
JSFiddle上的演示
您可以实现以下算法:
- 如果
a
和b
的长度不相同:- 返回
false
.
- 返回
- 否则:
- 克隆
b
, - 对于
a
中的每个项目:- 如果项目存在于我们的克隆
b
:- 从
b
的克隆中删除项目,
- 从
- 否则:
- 返回
false
.
- 返回
- 如果项目存在于我们的克隆
- 返回
true
.
- 克隆
在Javascript 1.6中,你可以使用every()和indexOf()来写:
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()
在内部使用严格相等(===
)。如果你真的想要非严格相等(==
),你将不得不写一个内循环。
就像这样?
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);
UPDATE
正如@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"的新属性,用于跟踪两个数组中的非基本元素。在函数返回之前删除这些元素,使数组元素保持不变。
这里小提琴
jsperf这里。
我更改jsperf测试用例的原因是,正如@Bergi所述,测试数组,特别是整个数组中只有2个唯一对象的事实不能代表我们要测试的内容。
这个实现的另一个优点是,如果你需要使它与pre IE9浏览器兼容,而不是使用defineProperty来创建一个不可枚举的属性,你可以使用一个普通的属性。
感谢大家的分享!我想出了下面的
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();
}
这不是最快的解决方案,但在我看来,这是迄今为止最具可读性的解决方案。
我不确定是否"==="是可以的,这个问题有点模糊…如果是这样,这比其他一些可能的方法要快得多,也简单得多:
function isSame(a,b){
return a.length==b.length &&
a.filter(function(a){ return b.indexOf(a)!==-1 }).length == b.length;
}
编辑2
1)感谢user2357112指出Object.prototype.toString.call
问题这也表明,它之所以这么快,是因为它没有考虑数组…
我修复了代码,它现在应该可以工作了:),不幸的是,它现在在chrome上大约59ops/s,在ff上大约45ops/s。
小提琴和JSPerf更新。
编辑
1)我修复了代码,它现在支持引用相同对象的多个变量。比以前慢了一点,但在chrome上仍然超过100ops/s。
2) 我尝试使用位掩码而不是数组来保持对象的多个位置,但它的速度接近15ops/s
3)正如在评论中指出的,我忘记重置tmp
后,[[get]]
被称为修复代码,小提琴,和perf。
所以感谢user2357112与他的回答这里的另一种方法使用计数
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(它使用与前面答案perf相同的数组a和b)与此代码对比编译的闭包
输出如下。注意:它不再支持深度比较了,
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
使用高效的查找表查找元素的计数:
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次)和没有重复的原始值不具有代表性。
- 需要帮助比较数组内的值,使用forEach循环
- 比较数组中的连续元素不会返回任何结果(javascript)
- 比较数组并使用条件对数组列表进行排序
- 比较数组JavaScript中的对象
- 比较数组中的元素,找出元素的最大和
- 使用JavaScript中的for each函数比较数组中的值
- 如何比较数组中的元素(javascript)
- 在 ie8 中使用茉莉花比较数组失败
- 比较数组慢
- 比较数组时遇到麻烦
- d3 本地存储比较数组 .filter 咖啡脚本;数组变量不起作用
- JavaScript 比较数组
- 如何声明和比较数组变量与其他选定变量
- 使用 .some() 比较数组
- 比较数组函数返回未定义
- 一个函数,用于比较数组中是否存在重复的数字
- Javascript 比较数组中的字符串
- 比较数组和 JSON 数据
- 在javascript中检查并比较数组中的数组
- 使用 indexOf() 比较数组中的字符