Implementing deep comparison in Javascript

I was reading through Eloquent JavaScript and one of the exercises is to write a function deepEqual that takes two values and returns true only if they are the same value or are objects with the same properties, where the values of the properties are equal when compared with a recursive call to deepEqual.

Let’s get started.

Note that both UnderscoreJS and Lodash have a toEqual method that can be used if you’re using one of these libraries.

JavaScript has both strict and type–converting comparisons.

The == operator compares objects by identity. === and !== are strict comparison operators. For strict equality the objects being compared must have the same type and:

  • Two strings are strictly equal when they have the same sequence of characters, same length, and same characters in corresponding positions.
  • Two numbers are strictly equal when they are numerically equal (have the same number value). NaN is not equal to anything, including NaN. Positive and negative zeros are equal to one another.
  • Two Boolean operands are strictly equal if both are true or both are false.
  • Two objects are strictly equal if they refer to the same Object.
  • Null and Undefined types are == (but not ===). [I.e. (Null==Undefined) is true but (Null===Undefined) is false]

Comparison Operators – MDN

Two objects are strictly equal if they refer to the same Object. In other words,  two distinct objects are never equal for either strict or abstract comparisons.

var obj1 = { 'key': 'value'}, ob2 = { 'key': 'value' }
obj1 === obj2 // false

To find out whether values should be compared directly or have their properties compared, we can use the typeof operator. If it produces “object” for both values, we should do a deep comparison. However we have to watch out for one major gotcha in JavaScript, because of a historical accident, ​typeof null also produces “object”.

With that, to test whether you are dealing with a real object will look something like typeof x == "object" && x != null. Let us write a function for that:

function isObject (obj) {
    if (typeof obj != "object" || obj == null) {
        return false
    }

    return true
}

Next test is to see whether both objects have the same properties. To be equal, both objects should have the same set of properties and each of these properties should contain the same value.

We can use Object.keys to go over the properties to test whether both objects have the same set of property names and whether those properties have identical values. One way to do that is to ensure that both objects have the same number of properties (the lengths of the property lists are the same).

if (Object.keys(obj1).length != Object.keys(obj2).length) {
    return false
}

And then, looping over one of the object’s properties to compare them, making sure the other actually has a property by that name. If they have the same number of properties and all properties in one also exist in the other, they have the same set of property names.  We compare the values of each property by letting the function recursively call itself in the for/in loop.

for (let prop in x) {
    if (!deepEqual(x[prop], y[prop])) {
        return false
    }
}

Returning the correct value from the function is best done by immediately returning false when a mismatch is found if not returning true at the end of the function.

Putting everything together, we have:

function deepEqual(x, y) {
    if (x === y) {
        return true
    } else if (isObject(x) && isObject(y)) {
        if (Object.keys(x).length != Object.keys(y).length) {
            return false
        }

        for (let prop in x) {
            if (!deepEqual(x[prop], y[prop])) {
                return false
            }
         }

        return true
    }
}

function isObject (obj) {
    if (typeof obj != "object" || obj == null) {
        return false
    }

    return true 
}

Testing the function:

let obj = {here: {is: "an"}, object: 2}

deepEqual(obj, obj) // true
deepEqual(obj, {here: 1, object: 2}) // false
deepEqual(obj, {here: {is: "an"}, object: 2}) // true

One more improvement we could make is to make the isObject function private.  It not used outside this function and unnecessarily gets added to the global scope.

We can hide a “private” function inside a function of this kind by placing one function declaration inside of another. The inner function is not hoisted out into the global scope, so it is only visible inside of the parent function. With that:

function deepEqual(x, y) {
    if (x === y) {
        return true
    } else if (isObject(x) && isObject(y)) {
        if (Object.keys(x).length != Object.keys(y).length) {
            return false
        }

        for (let prop in x) {
            if (!deepEqual(x[prop], y[prop])) {
                return false
            }
        }

        return true
    }

    function isObject (obj) {
        if (typeof obj != "object" || obj == null) {
            return false
        }

        return true
    }
}

Lastly, this StackOverflow question about determining equality of two JavaScript objects is a really great learning resource, do read.

 

Advertisements

TIOBE Programming Community Index

The TIOBE Programming Community index gives an indication of the popularity of programming languages. The index is updated once a month. The ratings are based on the number of skilled engineers world-wide, courses and third party vendors. The popular search engines Google, MSN, Yahoo!, and YouTube are used to calculate the ratings. Observe that the TIOBE index is not about the best programming language or the language in which most lines of code have been written.

The index can be used to check whether your programming skills are still up to date or to make a strategic decision about what programming language should be adopted when starting to build a new software system.

Since there are many questions about the way the TIOBE index is assembled, a special page is devoted to its definition.

The ratings are calculated by counting hits of the most popular search engines. The search query is executed for the regular Google, Google Blogs, MSN, Yahoo!, and YouTube web search for the last 12 months. The web site Alexa.com has been used to determine the most popular search engines.

The number of hits determine the ratings of a language. The counted hits are normalized for each search engine for the first 50 languages.

Besides the rating of programming languages, there is also a status indicated in the TIOBE chart. Programming languages that have status “A” are considered to be mainstream languages. Status “A-” and “A–” indicate that a programming language is between status “A” and “B”. If a programming language has a rating that is higher than 0.7% (yes, this number is arguable but we had to fix it somewhere) for at least 3 months it is rewarded status “A”. The first two months the programming language will receive status “A–” and “A-” respectively. The opposite holds for languages that go from status “A” to status “B”. So if a language had status “A” 2 months ago, a rating of “0.607%” last month and a rating of “0.687%” now, it will have status “A–“.

Programming languages that are very similar are grouped together. Currently the maximum of the hits of the individual languages is taken into account when calculating the ratings of groupings. In the future we will do a better job and take the union (from mathematical set theory) of all the hits.

The long term trends for the top 10 programming languages can be found in the line diagram below.

No wonder Java tops the ranking. And it will continue to hold that position for some time to come. What I am surprised to see there was Pascal is gaining popularity and people are using it nowadays. You can see the list of top 50 languages here.