比较数组作为（多）套 [英] Compare arrays as (multi-) sets

问题描述

我在寻找一种有效的方法，找出两个数组中是否含有相同数量相同的元素（在 == 意义上的），以任意顺序：

I'm looking for an efficient way to find out whether two arrays contain same amounts of equal elements (in the == sense), in any order:

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。需要注意的是pretty多线程中使用 === ，而不是 == 比较每一个解决方案。这是罚款，但我的需求。

PS. Note that pretty much every solution in the thread uses === and not == for comparison. This is fine for my needs though.

推荐答案

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

我延长了 code 拥有或者通过<$ C检查的可能性$ C>参考或平等

I extended the code to have the possibility of either checking by reference or equality

只是通过真正作为第二个参数做一个参考检查。

just pass true as second parameter to do a reference check.

此外，我添加了示例的 JSPerf

Also I added the example to Brunos JSPerf

• 它运行在约11 OPS /秒​​做一个参考检查

我会尽快（！）评论的code，因为我得到一些空闲时间来解释它多一点，但目前不具备的时候，SRY 。完成

I will comment the code as soon(!) as I get some spare time to explain it a bit more, but at the moment don't have the time for that, sry. Done

更新2

就像布鲁诺在评论中指出 sameElements（[NaN的]，[为NaN]）收益率假

Like Bruno pointed out in the comments sameElements([NaN],[NaN]) yields false

在我看来，这是正确的行为为 NaN的是ambigious，应始终导致假的结果，至少当比较 NaN.equals（NAN）。但他有相当不错的点。

In my opinion this is the correct behaviour as NaN is ambigious and should always lead to a false result,at least when comparing NaN.equals(NaN). But he had quite a good point.

无论

[1,2，富，酒吧，NaN时，3] 应该等于 [1,3，富大，NaN，酒吧， 2] 或没有。

好吧..说实话我有点撕裂它是否应该还是没有，所以我增加了两个标志。

Ok.. honestly I'm a bit torn whether it should or not, so i added two flags.

• Number.prototype.equal.NaN
  
  
  
  • 如果属实
    
    
    
    • NaN.equals（NAN）//真实
    
    
    • Number.prototype.equal.NaN
      • If true
        • NaN.equals(NaN) //true
        
        
        • 如果属实
          
          
          
          • [NaN的] .equals（[NaN的]，真）//真实
          
          
          • 的注意这是仅供参考的检查。作为一个深刻的检查将调用 Number.prototype.equals 反正的
          
          

          更新3：

          荡我完全错过了排序功能2行。

          Dang i totally missed 2 lines in the sort function.

          添加

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

          在105线的小提琴

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

          Which is kind of important as it determines the consistent order of the Elements.

          更新4 结果
          我试图优化排序功能位，并设法得到它高达约20 OPS /秒​​。

          Update 4
          I tried to optimize the sort function a bit, and managed to get it up to about 20 ops/s.

          下面是更新code，以及更新后的小提琴=）

          Below is the updated code, as well as the updated fiddle =)

          此外，我选择纪念排序功能外的对象，它似乎并没有做出性能差异了，而其更具可读性

          Also i chose to mark the objects outside the sort function, it doesn't seem to make a performance difference anymore, and its more readable

          下面是一个使用 Object.defineProperty 办法来添加等于功能

          Here is an approach using Object.defineProperty to add equals functions to

          数组，对象，数字，字符串，布尔的 原型，以避免在一个函数类型检查
          性能方面的原因。正如我们可以递归调用 .equals 任何元素。

          Array,Object,Number,String,Boolean's prototype to avoid typechecking in one function for performance reasons. As we can recursively call .equals on any element.

          不过，当然检查平等​​的对象可能会导致大对象的性能问题。

          But of course checking Objects for equality may cause performance issues in big Objects.

          的因此，如果有人感觉不愉快的操控本机的原型，只是做一个类型检查，并把它变成一个功能的

          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 函数，对于类型检查的费用。的

          Note. of course you could put all equal functions into the sameElements function, for the cost of the typechecking.

          现在这里有3个例子：1深检查，2参照检查

          Now here are 3 examples: 1 with deep checking, 2 with reference checking.

          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];
          

          因此​​，这些都是我们比较阵列。和输出

          So these are the Arrays we compare. And the output is

          
          

          1. 检查 A 和 B 与只引用。

          的console.log（sameElements（A，B，真））//真，因为它们含有相同的元素

          检查 B 和 C 与只引用

          的console.log（sameElements（B，C，真））//错误的，因为C包含两次吧。

          检查 B 和 C 深受

          的console.log（sameElements（B，C，FALSE））//如酒吧和foo的真实都是平等的，但不一样的

          检查包含NaN的2阵列

          Check for 2 Arrays containing NaN

          Array.prototype.equals.NaN = TRUE; 结果
          的console.log（sameElements（[NaN的]，[NaN的]，真实））; //真。结果
          Array.prototype.equals.NaN = FALSE;

          在 的jsfiddle

          Demo on JSFiddle

          这篇关于比较数组作为（多）套的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！