What is the most efficient way to determine if a collection of objects has changed?

Question

I've previously fetched a collection from the backend. I'm polling the backend for changes and have received another collection. The dataset is reasonable sized, so we don't need any optimizations... just fetched the whole thing again.

Running both datasets through algorithm f(previousCollection, newCollection), I would like to generate results for added, removed, and modified.

What is the most efficient way to do this? Or, better put, how do you all do this in your day to day work?

Example data:

old:

{id: 1, foo: 'bar'},
{id: 2, foo: 'bar'}

new:

{id: 2, foo: 'quux'},
{id: 4, foo: 'bar'}

expected result:

{event: 'removed', id: 1},
{event: 'modified', id: 2},
{event: 'added', id: 4}

Answer 1

Using Array#reduce and Array#find makes this quite simple

    function f(prev, curr) {
        var result = prev.reduce(function(result, p) {
            var c = curr.find(function(item) {
                return item.id == p.id;
            });
            if(c) {
                if(c.foo !== p.foo) {
                    result.push({event: 'modified', id:p.id});
                }
            } else {
                result.push({event: 'removed', id:p.id});
            }
            return result;
        }, []);
        return curr.reduce(function(result, c) {
            var p = prev.find(function(item) {
                return item.id == c.id;
            });
            if(!p) {
                result.push({event: 'added', id:c.id});
            }
            return result;
        }, result);
    }
    var old = [
        {id: 1, foo: 'bar'},
        {id: 2, foo: 'bar'}
    ];

    var curr = [
        {id: 2, foo: 'quux'},
        {id: 4, foo: 'bar'}
    ];
    console.log(f(old, curr));

Just for laughs, this example is written in ES2015+ using Arrow functions, object shorthand and object de-structuring

var f = (previousCollection, newCollection) => newCollection.reduce((result, {id}) => {
        if (!previousCollection.find(item => item.id == id)) {
            result.push({event: 'added', id});
        }
        return result;
    }, previousCollection.reduce((result, {id, foo}) => {
        var {foo:newValue} = newCollection.find(item => item.id == id) || {};
        if (newValue) {
            if(newValue !== foo) {
                result.push({event: 'modified', id});
            }
        } else {
            result.push({event: 'removed', id});
        }
        return result;
    }, []));

var old = [
    {id: 1, foo: 'bar'},
    {id: 2, foo: 'bar'}
];

var curr = [
    {id: 2, foo: 'quux'},
    {id: 4, foo: 'bar'}
];
console.log(f(old, curr));

Answer 2

This is more of a comprehensive comparison.

Possible Changes:

• Value of a property updated
• A new property added
• A property deleted. This can overlap value changed as value is different
• An object is deleted.
• A new object is added.

/*
  Status:
    Key Added,
    Key Deleted,
    Object Added,
    Object Deleted,
    Modified,
    Has Duplicate
*/
function getUpdates(old, newState) {
  var result = [];

  // Create new copies 
  old = old.slice(0);
  newState = newState.slice(0);

  // Deleted Objects
  mismatchingObjects(old, newState, result)

  old.forEach(function(o) {
    var report = {};
    report.id = o.id;
    var match = newState.filter(function(item) {
      return item.id === o.id
    });
    var mlen = match.length;
    if (mlen) {
      if(mlen === 1 && stringMatch(o, match[0])) return
      if(mlen > 1) report.hasDuplicate = true;
      match.forEach(function(m, index) {
        if (stringMatch(o, m)) return
        keyMatches(o, m, index, report)
        matchValue(o, m, index, report)
      })
    }
    if(Object.keys(report).length > 1)
     result.push(report)
  });
  return result
}

function stringMatch(o1, o2) {
  return JSON.stringify(o1) === JSON.stringify(o2);
}

function keyMatches(o1, o2, index, report) {
  var k1 = Object.keys(o1);
  var k2 = Object.keys(o2);
  if (k1.join() !== k2.join()) {
    report.keysRemoved = (report.keysRemoved || [])
    var r = k1.filter(function(k) {
      return k2.indexOf(k) < 0;
    });
    report.keysRemoved.push({
      keys: r,
      objectIndex: index
    });
    report.keysAdded = (report.keysAdded || [])
    var a = k2.filter(function(k) {
      return k1.indexOf(k) < 0;
    });
    report.keysAdded.push({
      keys: a,
      objectIndex: index
    })
  }
}

function matchValue(o1, o2, index, report) {
  report.keysChanged = report.keysChanged || [];
  var keys = [];
  for (var k in o1) {
    if (o1[k] !== o2[k] && o2[k]) {
      keys.push(k);
    }
  }
  report.keysChanged.push({
    keys: keys,
    objectIndex: index
  })
}

function mismatchingObjects(o1, o2, result) {
  var ids1 = o1.map(function(o) {
    return o.id
  });
  var ids2 = o2.map(function(o) {
    return o.id
  });
  ids1.forEach(function(id) {
    if (ids2.indexOf(id) < 0)
      result.push({
        id: id,
        status: "Object Deleted"
      })
  })

  ids2.forEach(function(id) {
    if (ids1.indexOf(id) < 0)
      result.push({
        id: id,
        status: "Object Added"
      })
  })
}

var old = [{
  id: 1,
  foo: 'bar'
}, {
  id: 2,
  foo: 'bar'
}, {
 id: 3,
  foo: "test",
  deletedKey: "bla bla"
}]
var newState = [{
  id: 2,
  foo: 'quux'
}, {
 id: 3,
  foo: "test",
  addedKey: "bla bla"
}, {
 id: 3,
  foo: "test2"
}, {
  id: 4,
  foo: 'bar'
}];

console.log(getUpdates(old, newState))

---

Note: This may seems a bit of an overkill. If you feel so, please accept my apologies.