9

我正在寻找一种有效的方法来确定两个数组是否==以任何顺序包含相同数量的相等元素（在某种意义上）：

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。请注意，线程中的几乎每个解决方案都使用===而不是==用于比较。不过，这对我的需求很好。

4

8 回答 8

7

更新 5 我用不同的方法发布了一个新的答案。

更新

我扩展了代码以有可能通过reference或检查equality

只需true作为第二个参数传递来进行参考检查。

我还将示例添加到Brunos JSPerf

  • 它以大约 11 ops/s 的速度运行，进行参考检查

我会尽快（！）评论代码，因为我有一些空闲时间来解释它，但目前没有时间，sry. 完毕

更新 2。

就像布鲁诺在评论中指出的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无论如何都会调用深度检查

更新 3：

当我完全错过了排序功能中的两行。

添加

 r[0] = a._srt; //DANG i totally missed this line
 r[1] = b._srt; //And this.

小提琴中的第 105 行

这很重要，因为它决定了元素的一致顺序。

更新 4
我尝试稍微优化排序功能，并设法将其提高到大约 20 ops/s。

下面是更新的代码，以及更新的小提琴 =)

我还选择在排序函数之外标记对象，它似乎不再对性能产生影响，而且它更具可读性

这是一种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];

所以这些是我们比较的数组。输出是

  1. 仅检查a和b参考。

    console.log (sameElements ( a,b,true)) //true As they contain the same elements

  2. 仅检查b和c参考

    console.log (sameElements (b,c,true)) //false as c contains bar twice.

  3. 检查b并c深入

    console.log (sameElements (b,c,false)) //true as bar and foo are equal but not the same

  4. 检查 2 个包含 NaN 的数组

    Array.prototype.equals.NaN = true;
    console.log(sameElements([NaN],[NaN],true)); //true.
    Array.prototype.equals.NaN = false;

JSFiddle上的演示

于 2013-06-04T10:41:22.087 回答
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);
于 2013-06-04T09:14:34.840 回答
2

您可以实现以下算法：

  • 如果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()使用严格相等 ( ===)。如果你真的想要非严格相等（==），你将不得不编写一个内部循环。

于 2013-06-04T09:16:13.913 回答
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”的新属性，用于跟踪两个数组中的非原始元素。这些在函数返回之前被删除，以便像以前一样保留数组元素。

在这里提琴

jsperf在这里。

我更改 jsperf 测试用例的原因是，正如@Bergi 所说的测试数组，特别是整个数组中只有 2 个唯一对象这一事实并不代表我们正在测试的内容。

此实现的另一个优点是，如果您需要使其与 IE9 之前的浏览器兼容，而不是使用 defineProperty 创建不可枚举的属性，您可以只使用普通属性。

于 2013-06-04T10:20:12.040 回答
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();
}

这不是最快的解决方案，但 IMO 是迄今为止最易读的解决方案。

于 2013-06-05T08:55:06.803 回答
1

我不确定“===”是否可以，这个问题有点模糊......如果是这样，这比其他一些可能的方法要快得多，也更简单：

function isSame(a,b){
  return a.length==b.length && 
      a.filter(function(a){ return b.indexOf(a)!==-1 }).length == b.length;
}
于 2013-06-20T21:32:33.980 回答
1

编辑 2
1）感谢 user2357112 指出Object.prototype.toString.call这也显示的问题，原因是它这么快，它没有考虑数组......

我修复了代码，它现在应该可以工作了:)，不幸的是，它现在在 chrome 上约为 59ops/s，在 ff 上约为 45ops/s。

Fiddle 和 JSPerf 已更新。

编辑
1）我修复了代码，它现在支持引用同一个对象的多个变量。比以前慢一点，但在 chrome 上仍然超过 100ops/s。

2） 我尝试使用位掩码而不是数组来保持对象的多个位置，但它的速度接近 15ops/s

3)正如评论中指出的那样，我忘记在修复代码、小提琴和性能tmp后重置。[[get]]

因此，感谢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
于 2013-06-21T07:17:56.080 回答
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 次）并且没有重复的原始值不具有代表性。

于 2013-06-04T13:26:10.940 回答