467,921 Members | 1,223 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Share your developer knowledge by writing an article on Bytes.

Optimize Loops to Compare Two Arrays

gits
Expert Mod 4TB
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.

Expand|Select|Wrap|Line Numbers
  1. var list1 = [1, 2, 3, 4, 5, 6];
  2. var list2 = ['a', 'b', 'c', 3, 'd', 'e'];
  3.  
  4. for (var i in list1) {
  5.     for (var j in list2) {
  6.         if (list1[i] == list2[j]) {
  7.             alert('found ' + list1[i] + ' in both lists');
  8.         }
  9.     }
  10. }
  11.  
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:

Expand|Select|Wrap|Line Numbers
  1. var list1 = [1, 2, 3, 4, 5, 6];
  2. var list2 = ['a', 'b', 'c', 3, 'd', 'e'];
  3.  
  4. outerloop: for (var i in list1) {
  5.     for (var j in list2) {
  6.         if (list1[i] == list2[j]) {
  7.             alert('found ' + list1[i] + ' in both lists');
  8.             break outerloop;
  9.         }
  10.     }
  11. }
  12.  
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:

Expand|Select|Wrap|Line Numbers
  1. var list1 = [1, 2, 3, 4, 5, 6];
  2. var list2 = ['a', 'b', 'c', 3, 'd', 'e'];
  3. var lookup = {};
  4.  
  5. for (var j in list2) {
  6.     lookup[list2[j]] = list2[j];
  7. }
  8.  
  9. for (var i in list1) {
  10.     if (typeof lookup[list1[i]] != 'undefined') {
  11.         alert('found ' + list1[i] + ' in both lists');
  12.         break;
  13.     } 
  14. }
  15.  
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:

Expand|Select|Wrap|Line Numbers
  1. var lookup = {
  2.     'a': 'a',
  3.     'b': 'b',
  4.     'c': 'c',
  5.     '3': '3',
  6.     'd': 'd',
  7.     'e': 'e'
  8. };
  9.  
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.
Aug 27 '07 #1
  • viewed: 34141
Share:

Sign in to post your reply or Sign up for a free account.

Similar topics

2 posts views Thread by nobs | last post: by
3 posts views Thread by Lance | last post: by
1 post views Thread by Jacob Thastrup | last post: by
8 posts views Thread by Turbot | last post: by
blyxx86
5 posts views Thread by blyxx86 | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.