Custom implementation of comparing two non ordered array of object in Javascript

Question

I want to compare two array of objects, they should be considered equal if their elements are same but not in same order. e.g. [{a:1}, {b:2}] and [{b:2}, {a:1}]

I am using lodash-v3's isEqual which can compare two values but it only gives true if the order in array is same, so I've implement one function that compares elements recursively.

function deepEqual(data1, data2) {
  data1 = _.cloneDeep(data1);
  data2 = _.cloneDeep(data2);
  function isDeepEqual(val1, val2) {
    if (_.isArray(val1) && _.isArray(val2)) {
      if (val1.length === val2.length) {
        for (let id1 in val1) {
          let hasMatch = false;
          let matchOnIndex = -1;
          for (let id2 in val2) {
            if (isDeepEqual(val1[id1], val2[id2])) {
              hasMatch = true;
              matchOnIndex = id2;
              break;
            }
          }
          if (hasMatch) {
            val2.splice(matchOnIndex, 1);
          } else {
            return false;
          }
        }
        return true;
      } else {
        return false;
      }
    }

    if (_.isPlainObject(val1) && _.isPlainObject(val2)) {
      if (Object.keys(val1).length === Object.keys(val2).length) {
        for (let temp1 in val1) {
          if (!isDeepEqual(val1[temp1], val2[temp1])) {
            return false;
          }
        }
        return true;
      } else {
        return false;
      }
    }
    return _.isEqual(val1, val2);
  }

  return isDeepEqual(data1, data2);
}

Above function works, but how can i improve it performance wise? If there is any simple implementation with lodash3 that works for me as well.

Link to above function's fiddle.

EDIT:

The two array of objects can be nested, e.g.

[{
  a:1,
  b:[{
    c: [1, 2]
  },
  {
    d: [3, 4]
  }]
},{
  e:1,
  f:[{
    g: [5, 6]
  },
  {
    h: [7, 8]
  }]
}]

and

[{
  e:1,
  f:[{
    h: [8, 7]
  },{
    g: [6, 5]
  }]
},{
  a:1,
  b:[{
    d: [4, 3]
  },{
    c: [2, 1]
  }]
}]

Arrays can also not have unique values(as users are creating this arrays).

This might be possible with _.isEqualWith as @Koushik and @tokland suggested. Unfortunately it's available from lodashv4 so I can't use it. Similar solution is also mentioned in this comment.

Really sorry for not clearly specifying the examples. The fiddle has all different type of cases.

Use count sort to compare content of array. This will give you O(n) instead of O(n^2) you currently have. — miradham, Jul 30 '18 at 10:09
@miradham, can you please give me a simple example or algorithm of how to compare two array of objects with count sort? I thought it only works with array of numbers. — Riddhesh, Jul 31 '18 at 18:21
by count sort, I meant, you could hash values and check its amount and stored value only once. But I was wrong saying that it could improve performance. In your example object with same key can have multiple values, so you have to check every value, which gives you O(n^2) anyway. — miradham, Aug 01 '18 at 05:21

score 0 · Answer 1 · answered Jul 30 '18 at 12:27

i think this is what you want

var first = [{ a: 1 }, { b: 2 }];
        var second = [{ b: 2 }, { a: 1 }];
function comparer(otherArray){
  return function(current){
    return otherArray.filter(function(other){
      return other.a == current.a && other.b == current.b
    }).length == 0;
  }
}
var onlyInA = first.filter(comparer(second));
var onlyInB = second.filter(comparer(first));
result = (onlyInA.concat(onlyInB)).length===0;
console.log(result);

tokland · Answer 2 · 2018-07-31T18:26:32.853

Function _.isEqualWith should be the starting point. Now, there are many ways you can implement it. You could make it pretty efficient by defining an ordering for the items in the arrays. An example using id as a key:

function isEqualConsideringArraysAsSets(obj1, obj2, key) {
  const customizer = (objValue, othValue) => {
    if (_(objValue).isArray() && _(othValue).isArray()) {
      return _.size(objValue) === _.size(othValue) &&
        _.zip(_.sortBy(objValue, key), _.sortBy(othValue, key))
          .every(([val1, val2]) => isEqualConsideringArraysAsSets(val1, val2));
    }
  };

  return _.isEqualWith(obj1, obj2, customizer);
}

console.log(isEqualConsideringArraysAsSets([{id: 1}, {id: 2}], [{id: 2}, {id: 1}], "id"))

`_.zip`. You are missing the `.` – smac89 Jul 31 '18 at 18:24 — smac89, Jul 31 '18 at 18:24

score 0 · Answer 3 · answered Jul 30 '18 at 15:28

how about simply check each Object of one array presents in another array and having same length (both array)?

let isEqualArray = (arr1, arr2) => (
        arr1 === arr2 ||    
        arr1.length === arr2.length && 
        !arr1.some(a=> !arr2.find(b=>_.isEqual(a,b)))
)

let a1 = [{a:1}, {b:2}],
    a2 = [{b:2}, {a:1}];
    
let isEqualArray = (arr1, arr2) => (
  arr1 === arr2 || 
    arr1.length === arr2.length && 
  !arr1.some(a=> !arr2.find(b=>_.isEqual(a,b)))
)

console.log(isEqualArray(a1,a2));

<script src="https://cdnjs.cloudflare.com/ajax/libs/lodash.js/4.17.10/lodash.min.js"></script>

Usage of _.isEqual or _.isEqualWith with a customizer depending on how you want to compare two object!

Note: this will not work 100% when you have duplicate items in your array, but it will atleast confirm that all the items of one array is present on another array. You can do a reverse check, or apply unique to perform this compare for duplicate arrays.

Custom implementation of comparing two non ordered array of object in Javascript

3 Answers3