Efficient way to compare two arrays

Question

I am using two arrays to accomplish a task of checking if values in array1 exist in array2. If so remove the content in array1 and keep checking till array1 is empty. If they dont exist just return from the function. I am using Javascript

I implemented it using classic two for loops which gives a run time of o(n*2). I would like to know if there is any other efficient way to perform this operation using any other data structure that javascript supports. Below is my current implementation

for(var j = 0; j < tempArray.length; j++){
     for(var k = 0; k < this.probsSolved.length; k++){
         if(tempArray[j] == this.probsSolved[k]){
             tempArray.splice(j,1);            
             if(tempArray.length <= 0){
                 this.updateAchievements(achID);
                 this.storage.set(achKey,1);
                 return;
             }         
     }
}

The thing is I have to call the function under which this operation is performed every 5 seconds and this for me looks highly inefficient.

Could someone suggest a better algorithm or a data structure that performs better than the one above that I can use and how would I use if so.

Answer 1

Putting the elements of array2 in a dictionary data-structure (to ensure that lookup is quick) might help.

See How to do associative array/hashing in JavaScript

In pseudo-code, I would approach like the following:

dict = {}

foreach elem in array2:
    insert elem in dict

foreeach elem in array1:
    if elem in dict:
        remove elem from array1

Answer 2

Adding an alternative answer, as this will still be relevant to many of us. I found this question when searching for a way to optimise a script that compares two arrays where both have tens of thousands of keys.

In my situation, it forms part of a Google Script, and was exceeding the maximum execution time (~5 minutes) with typical datasets. Making the change below reduced the execution time below 10 seconds.

Inefficient comparison (maximum i*j iterations):

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');
        }
    }
}

Efficient comparison (maximum i+j iterations)

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;
    } 
}

Found here: https://bytes.com/topic/javascript/insights/699379-optimize-loops-compare-two-arrays