Optimize Loops to Compare Two Arrays

[gits]

This little article will show you how to optimize runtime performance when you need to compare two arrays (a quite common task). Have a close look at the entire article, and you will see the advantage of the final code snippet :)

Let's assume we want to find out the element that is contained by both of the lists.

var list1 = [1, 2, 3, 4, 5, 6];
var list2 = ['a', 'b', 'c', 3, 'd', 'e'];
 
for (var i in list1) {
    for (var j in list2) {
        if (list1[i] == list2[j]) {
            alert('found ' + list1[i] + ' in both lists');
        }
    }
}
 

It's a good idea to break out of the entire loop when the inner condition returns true, so you will get even faster execution if you do the following:

var list1 = [1, 2, 3, 4, 5, 6];
var list2 = ['a', 'b', 'c', 3, 'd', 'e'];
 
outerloop: for (var i in list1) {
    for (var j in list2) {
        if (list1[i] == list2[j]) {
            alert('found ' + list1[i] + ' in both lists');
            break outerloop;
        }
    }
}
 

But have in mind that this is not the best way to compare two arrays!

By using two loops, you have up to n*m steps to perform. But we can do better than that! How about n+m, hmm? ;)

Have a look at the following implementation:

var list1 = [1, 2, 3, 4, 5, 6];
var list2 = ['a', 'b', 'c', 3, 'd', 'e'];
var lookup = {};
 
for (var j in list2) {
    lookup[list2[j]] = list2[j];
}
 
for (var i in list1) {
    if (typeof lookup[list1[i]] != 'undefined') {
        alert('found ' + list1[i] + ' in both lists');
        break;
    } 
}
 

Since it is much faster to search for an element in an array by its key rather than its value, we create an index array, 'lookup', and copy all of the values from list2 as keys in lookup. When this code executes, lookup looks like this:

var lookup = {
    'a': 'a',
    'b': 'b',
    'c': 'c',
    '3': '3',
    'd': 'd',
    'e': 'e'
};
 

Now it becomes a simple matter of running through list1 and checking to see if there is a matching index in lookup, which is MUCH faster than looping through list2!

Good luck and kind regards.