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

Understanding Big O notation

An algorithm refers to a process for going about a particular operation. Often, there is more than one way to achieve a particular computing goal. The selection of a particular algorithm can make our code either fast or slow – even to the point where it stops working under a lot of pressure.

One way to analyze competing algorithms is to count the number of steps each one takes. The number of steps that an algorithm takes is the primary factor in determining its efficiency.

In order to ease communication regarding time complexity, computer scientists have borrowed a concept from the world of mathematics to describe a concise and consistent language around the efficiency of data structures and algorithms. Known as Big O Notation, this formalized expression around these concepts allows us to easily categorize the efficiency of a given algorithm and convey it to others.

the-big-oh

Big O achieves consistency by focusing on the number of steps that an algorithm takes.

O(1)

Many pronounce this verbally as “Big Oh of 1”, others call it “Order of 1”. While there is no standardized way to pronounce Big O Notation, there is only one way to write it.

O(1) simply means that the algorithm takes the same number of steps no matter how much data there is. For example, reading from an array takes just one step no matter how much data the array contains. On an old computer, that step may have taken twenty minutes, and on modern hardware, it may take just a nanosecond. But in both cases, the algorithm takes just one single step.

O(N)

This is a way of saying that for N elements inside an array, the algorithm would take N steps to complete.

Big O Notation does more than simply describe the number of steps that an algorithm takes, rather, it describes how many steps an algorithm takes based on the number of data elements that the algorithm is acting upon. Another way of saying this is that Big O answers the following question: how does the number of steps change as the data increases?

An algorithm that is O(N) will take as many steps as there are elements of data. So when an array increases in size by one element, an O(N) algorithm will increase by one step. An algorithm that is O(1) will take the same number of steps no matter how large the array gets. Because the number of steps remains constant at O(1) no matter how much data there is, this would be considered constant time. Even if an algorithm technically takes 3 or 5 steps rather than just 1 step, Big O Notation considers this algorithm as O(1) as long as the number of steps remains constant. It follows that even a 100 step algorithm would be expressed as O(1).

The best-case scenario of an algorithm refers to the time an algorithm performs at its best and takes as fewer steps as possible to perform an operation. Like inserting an element at the end of an array. In contrast, the worst-case scenario refers to the worst performing time.

While Big O effectively describes both the best- and worst-case scenarios of a given algorithm, Big O Notation generally refers to worst-case scenario unless specified otherwise. The reason for this would be that knowing exactly how inefficient an algorithm can get in a worst-case scenario prepares us for the worst and may have a strong impact on our choices.

There are also algorithms that fall somewhere in between O(1) and O(N). In Big O, these algorithms are described as having a time complexity of O(log N). These type of algorithms are known as having a time complexity of log time.

Simply put, O(log N) is the Big O way of describing an algorithm that increases one step each time the data is doubled.

To understand why a given algorithm is called “O(log N)”, we need to first understand what logarithms are. Log is shorthand for logarithm. The first thing to note is that logarithm has nothing to do with algorithms, even though the two words look and sound similar. Logarithms are the inverse of exponents. Here’s a quick refresher on what exponents are:

23 is equivalent to, 2 * 2 * 2, which just happens to be 8.

Now, log2 8 is the converse of the above. It means, how many times do you have to multiply 2 by itself to get a result of 8?

Since you have to multiply 2 by itself 3 times to get 8, log2 8 = 3.

Here’s another example:

26 translates to: 2 * 2 * 2 * 2 * 2 * 2 = 64

Since, we had to multiply 2 by itself 6 times to get 64, log2 64 = 6.

There is an alternative way of describing the same concept to wrap our heads around this more easily.

Another way of explaining log2 8 is: if we kept dividing 8 by 2 until we ended up with 1, how many 2s would we have in our equation?

8 / 2 / 2 / 2 = 1

In other words, how many times do we need to divide 8 by 2 until we end up with 1?

In this example, it takes us 3 times. Therefore, log2 8 = 3.

Similarly, we could explain log2 64 as: how many times do we need to halve 64 until we end up with 1?

64 / 2 / 2 / 2 / 2 / 2 / 2 = 1

Since there are 6 2s, log2 64 = 6.

Here’s a simple JavaScript function to determine the logarithm of a given number:

function log2(num) {
  var count = 0
  while (num > 1) {
    num = num / 2
    count++
  }

  return count
}

Now that we understand what logarithms are, the meaning behind O(log N) will become clear.

Whenever we say O(log N), it’s actually shorthand for saying O(log2 N). We’re just omitting that small 2 for convenience.

Recall that O(N) means that for N data elements, the algorithm would take N steps. If there are eight elements, the algorithm would take eight steps.

O(log N) means that for N data elements, the algorithm would take log2 N steps. So, if there eight elements, the algorithm would take three steps, since log2 8 = 3.

Said another way, if we keep dividing the eight elements in half, it would take us three steps until we end up with one element.

While the O(N) algorithm takes as many steps as there are data elements, the O(log N) algorithm takes just one additional step every time the data elements are doubled.

This was an easy-to-understand approach to the topic of Big O. Big O is originally a concept of mathematics, and therefore it is often described in mathematical terms. For example,

The big-Oh notation allows us to say that a function f(n) is less than or equal to another function g(n) up to a constant factor and in the asymptotic sense as n grows towards infinity. If f(n) is of the form of An + B, where A and B are constants. It’s called a linear function, and it is O(n).

The big-Oh notation gives an upper bound on the growth rate of a function. The statement “f(n) is O(g(n))” means that the growth rate of f(n) is no more than the growth rate of g(n).

For further reading and to dig further into the math behind Big O, check out:

 

Data binding and flow in VueJS

Two way data binding means that UI fields are bound to model data dynamically such that when a UI field changes, the model data changes with it and vice-versa.

One way data flow means that the model is the single source of truth. Changes in the UI trigger messages that signal user intent to the model (or “store” in React). Only the model has the access to change the app’s state.

The effect is that data always flows in a single direction, which makes it easier to understand.

One way data flows are deterministic, whereas two-way binding can cause side-effects which are harder to follow and understand.

vue logoIn Vue, All props form a one-way-down binding between the child property and the parent one: when the parent property updates, it will flow down to the child, but not the other way around. This prevents child components from accidentally mutating the parent’s state, which can make your app’s data flow harder to understand.

In addition, every time the parent component is updated, all props in the child component will be refreshed with the latest value. This means you should not attempt to mutate a prop inside a child component. If you do, Vue will warn you in the console.

However, there could be use cases where it would be necessary to mutate a prop:

  1. The prop is used to pass in an initial value; the child component wants to use it as a local data property afterwards. In this case, it’s best to define a local data property that uses the prop as its initial value:
    props: ['initialCounter'],
    data: function () {
      return {
        counter: this.initialCounter
      }
    }
  2. The prop is passed in as a raw value that needs to be transformed. In this case, it’s best to define a computed property using the prop’s value:
    props: ['size'],
    computed: {
      normalizedSize: function () {
        return this.size.trim().toLowerCase()
      }
    }
    

 

Arrays Vs. Lists in Python

In the exploration of Python, I discovered a subtle but interesting difference between Arrays and Lists in Python.

Image result for python difference between array and list

Arrays and lists are both used in Python to store data, but they don’t serve exactly the same purposes. They both can be used to store any data type (real numbers, strings, etc), and they both can be indexed and iterated through, but the similarities between the two end there.

The array.array type is just a thin wrapper on C arrays. It can hold only homogeneous data, all of the same type, and so it uses only sizeof(one object) * length bytes of memory. Mostly, you should use it when you need to expose a C array to an extension or a system call (for example, ioctl or fctnl).

This is how you’d define an array:

import array
x = array.array('i', [1, 2, 3])

The array module defines an object type which can compactly represent an array of basic values: characters, integers, floating point numbers. Arrays are sequence types and behave very much like lists, except that the type of objects stored in them is constrained. The type is specified at object creation time by using a type code, which is a single character. Like the 'i' type code corresponds to Python’s int and 'b' type code corresponds to char etc.

array.array is also a reasonable way to represent a mutable string in Python 2.x (array('B', bytes)). However, Python 3.x offers a mutable byte string as bytearray.

Python Lists, on the other hand, are very flexible and can hold completely heterogeneous, arbitrary data, and they can be appended to very efficiently, in amortized constant time. If you need to shrink and grow your array time-efficiently and without hassle, they are the way to go. But they use a lot more space than C arrays.

It does take an extra step to use arrays because they have to be declared while lists don’t because they are part of Python’s syntax, so lists are generally used more often between the two, which works fine most of the time.

However, if you want to do the math on a homogeneous array of numeric data, then you’re much better off using NumPy, which can automatically vectorize operations on complex multi-dimensional arrays.

To make a long story short: array.array is useful when you need a homogeneous C array of data for reasons other than doing the math, like you may consider using arrays if you’re storing a large amount of data since arrays will store your data more compactly and efficiently.

Improving Web performance via image optimization

Web performance refers to the speed at which web pages are downloaded and displayed on the user’s web browser.

Faster website download speeds have been shown to increase visitor retention and loyalty and user satisfaction, especially for users with slow internet connections and those on mobile devices. Some aspects which can affect the speed of page load include browser/server cache, image optimization, and encryption (for example SSL), which can affect the time it takes for pages to render.

Images often account for most of the downloaded bytes on a web page and also often occupy a significant amount of visual space. As a result, optimizing images can often yield some of the largest byte savings and performance improvements for your website: the fewer bytes the browser has to download, the less competition there is for the client’s bandwidth and the faster the browser can download and render useful content on the screen.

image-optimization

Image Optimization

Image optimization is an art that you want to master. Optimizing web images is a process of delivering the high-quality images in the right format, dimension, size, and resolution while keeping the smallest possible size without sacrificing quality so that your page load times remain low. It’s also about image SEO. That is, getting your product images and decorative images to rank on Google and other image search engines.

The importance of images in connecting users to your products has been proven. If your website takes more than 3 seconds to load, users are more likely to abandon it which will drastically increase your bounce rate and eventually, it will affect your conversions.

How to optimize images?

Image optimization can be done in different ways be it by resizing the images, caching or by compressing the size. One of the simplest and most effective image optimization techniques is to ensure that we are not shipping any more pixels than needed to display the asset at its intended size in the browser.

There are numerous online tools you can use for image editing. Adobe even has a free image editing application for smartphones and tablets, Photoshop Express. This tool doesn’t have all of the capabilities of the desktop version of Adobe Photoshop, but it covers all the basics of image editing and doesn’t cost an arm and a leg.

Online image editing tools:

  • PicMonkey has been described by experts as a “staggeringly great photo editing tool”.
  • PIXLR is super user-friendly and comes with a 100% free app for your smartphone so you can edit on the go.
  • Canva is another fairly advanced online image editor.

Powerful image processing on the fly:

If you want responsive images on the fly Imgix is a great tool to try. Imgix transforms, optimizes, and intelligently caches your entire image library for fast websites and apps using simple and robust URL parameters. Resizing, cropping, and automatic content negotiation and enhancement are just the beginning of what you can do. Using Imgix, you can overlay text, stylize images, apply masks, add borders and padding, and much more.

In this digital world, every factor related to your website performance matters. And the expectation of visitors is only going to increases with time. One can not ignore the amazing benefits of optimizing images. These benefits are not restricted to the page load speed and SEO ranking only. Image optimization is capable of turning up your conversion and revenue numbers.

Connecting to a PostgreSQL server remotely through pgAdmin

It is a 3 step process to connect to a PostgreSQL server remotely through pgAdmin3.

Note: These steps are tested on Ubuntu 16.04 and PostgreSQL 8.4.

  1. You have to make PostgreSQL listening for remote incoming TCP connections because the default settings allow to listen only for connections on the loopback interface. To be able to reach the server remotely you have to add the following line into the file /etc/postgresql/8.4/main/postgresql.conf:

    listen_addresses = ‘*’

  2. PostgreSQL by default refuses all connections it receives from any remote address, you have to relax these rules by adding this line to /etc/postgresql/8.4/main/pg_hba.conf:

    host all all 0.0.0.0/0 md5

    This is an access control rule that let anybody login in from any address if he can provide a valid password (the md5 keyword). You can use needed network/mask instead of 0.0.0.0/0 .

  3. When you have applied these modifications to your configuration files you need to restart PostgreSQL server. Now it is possible to login to your server remotely, using the username and password.

To start PostgresSQL server you would do sudo /etc/init.d/postgresql stop and sudo /etc/init.d/postgresql start.

 

Target IE6 and IE7 Browsers without Conditional Comments

Need to target IE browsers? Here is a quick hack that doesn’t require conditional comments (note that your CSS will therefore not pass auto-validation, which is fine if you are aware of why it doesn’t).

The code below will change the background-color of divs depending on what browser the user is viewing the web page under. Since * cascades down to IE7 and below, we use _ after that declaration so that IE6 (and below) has a different background colour from IE7.

div {
    background-color: #999; /* all browsers */
    *background-color: #ccc; /* add a * before the property - IE7 and below */
    _background-color: #000; /* add a _ before the property - IE6 and below */
}