How to find common properties between JavaScript objects

Question

What is the best/most efficient way to find the common/different properties of an array of objects.

I need to identify the set of properties that exists in all objects and all have the same value(the common). Preferably I would also like to get an array with all other properties (the diff).

I have searched for an efficient library/function that can do it. But didn't find anything. So I tried on my own.

Consider this array of JS objects:

var objects = [{
    id: '2j2w4f',
    color: 'red',
    height: 20,
    width: 40,
    owner: 'bob'
}, {
    id: '2j2w3f',
    color: 'red',
    height: 20,
    width: 41,
    owner: 'bob'
}, {
    id: '2j2w2f',
    color: 'red',
    height: 21,
}, {
    id: '2j2w1f',
    color: 'red',
    height: 21,
    width: 44
}];

I would like to identify color (with value red) as the only common property. Note that they do not have the same set of properties. E.g. owner is not a common property.

This is my own attempt to solve it (using lodash):

function commonDifferentProperties(objects) {
    // initialize common as first object, and then remove non-common properties.
    var common = objects[0];
    var different = [];
    var i, obj;

    // iterate through the rest (note: i === 0 is not supposed to be covered by this)
    for (i = objects.length - 1; i > 0; i--) {
        obj = objects[i];
        // compare each property of obj with current common
        _.forOwn(obj, function (value, key) {
            // if property not in current common it must be different
            if (_.isUndefined(common[key])) {
                if (!_.contains(different, key)) {
                    different.push(key);
                }
            } else if (common[key] !== value) { // remove property from common if value is not the same
                delete common[key];
                different.push(key);
            }
        });

        // check that all properties of common is present in obj, if not, remove from common.
        _.forOwn(common, function (value, key) {
            if (_.isUndefined(obj[key])) {
                delete common[key];
                different.push(key);
            }
        });

    }

    return {
        common: common,
        different: different
    };
}

jsFiddle with the example

I have also tried a mapReduce approach, but that seemed even worse.

I still think this seems a bit complex/time consuming, and I will do this on 1000-10000 objects or more with 20-50 properties each.

Any suggestions?

Answer 1

There are two things that are look wrong in your solution:

• By var common = objects[0]; you don't copy the object, so you're going to corrupt the objects
• You both check that all properties of common is present in obj, but also compare each property of obj with current common. That seems to be once too much. Didn't realize at first that you needed the different properties as well.

I'd loop over the data in two passes. In the first, you collect all apparent properties in one object, in the second you test whether they're common or not:

function commonDifferentProperties(objects) {
    var common = _.reduce(objects, function(acc, obj) {
        for (var p in obj)
            acc[p] = obj[p];
        return acc;
    }, {});
    var different = _.reduce(objects, function(acc, obj) {
        for (var p in common)
            if (common[p] !== obj[p]) {
                delete common[p];
                acc.push(p);
            }
        return acc;
    }, []);
    return {
        common: common,
        different: different
    };
}

Answer 2

Here's what I did using just vanilla JS:

function commonDifferentProperties(objects) {
    var common = JSON.parse(JSON.stringify(objects[0]));
    var unmatchedProps = {};
    for (var i = 1; i < objects.length; i++) {
        for (var prop in objects[i]) {
            checkProps(objects[i],common,prop);
        }
        for (var commProp in common) {
            checkProps(common,objects[i],commProp);
        }
    }
    console.log(common);            // this is all the matched key/value pairs
    console.log(unmatchedProps);    // this is all the unmatched keys

    return { common: common, different: unmatchedProps };

    function checkProps(source, target, prop) {
        if (source.hasOwnProperty(prop)) {
            var val = source[prop];
            if (!target.hasOwnProperty(prop) || target[prop] !== val) {
                unmatchedProps[prop] = true;     // note: you could extend this to store values, or number of times you found this key, or whatever
                delete common[prop];
            }
        }
    }
}

http://jsfiddle.net/TwbPA/

So I copy the first object and use that to keep track of keys and values that are common. Then I iterate through all the other objects in your array and first look through all the key/values in the common object and compare to the current, deleting any missing properties from the common object if they are not in the current one, then I do the reverse to catch any properties in the current object that aren't in the common (or are in the current, but have the wrong value).

Answer 3

Edit

Sorry, i was in a hurry and didn't had enough time to think about it. Indeed, there's no need for a sort. I was thinking using a binary algorithm or something..

Here, the updated code without the sort. Console.time() gave me '3ms'. I'm doing similar to Bergi's solution, but instead of collecting all apparant properties i search for the element that has the fewest amount of properties. This reduces the amount of iterations on the second loop.

I've based the code on the following:

• if object X has a property the selected object doesn't have, then it isn't a common property!
• Thus the selected object has all common properties + extra's.
• The selected object has the fewest properties, thus the iterations of validating is less.

http://jsfiddle.net/kychan/cF3ne/1/

//    returns the common properties of given array.
function getCommonProps(objects)
{
    //    storage var for object with lowest properties.
    var lowest = {obj:null, nProperties:1000};

    //    search for the object with lowest properties. O(n).
    for (var j in objects)
    {
        var _nProp = Object.keys(objects[j]).length;

        if (_nProp < lowest.nProperties)
            lowest = {obj:objects[j], nProperties:_nProp};
    }

    //    var that holds the common properties.
    var retArr = [];

    //    The object with the fewest properties should contain common properties.
    for (var i in lowest.obj)
        if (isCommonProp(objects, i))    retArr.push(i);

    return retArr;
}

//    Checks if the prop exists in all objects of given array.
function isCommonProp(arr, prop)
{
    for (var i in arr)
    {
        if (arr[i][prop]===undefined)
            return false;
    }

    return true;
}

console.time('getCommonProps()_perf');
console.log(getCommonProps(objects));
console.timeEnd('getCommonProps()_perf');

Answer 4

Here's another approach that uses reduce() and transform():

_.reduce(objects, function(result, item) { 
    if (_.isEmpty(result)) {
        return _.assign({}, item);
    }

    return _.transform(item, function(common, value, key) {
        if (result[key] === value) {
            common[key] = value;
        }
    }, {});
}, {});