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.

Polyadelphous

What is the type of the elements in the arrays? Are the arrays in any particular order? – Ander

The suggested dictionary approach is a good one. Another is to sort both lists and then walk them in order much like you'd do a standard merge. That said, if your lists aren't very large then your "inefficient" method will be plenty fast enough. – Underfoot

my lists contain integer values and they would at max contain 50 values but the thing is I have to run this operation every 5 seconds. So the searching is practically done every 5 seconds until the first list goes empty. I would look into dictionaries though – Polyadelphous

With arrays of max size 50, you're talking a maximum of 2,500 iterations. The time that's going to take will be measured in milliseconds. Doing that once every five seconds will be no problem at all. – Underfoot

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

Hounding

else: return "Not equal". And in the end: if dict not empty: return "Not equal" – Astrodynamics

Thanks I will try using this idea! – Polyadelphous

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

Skirmish

Answer 3

Based on the other answers, I wrote a TS solution that has the same complexity and is compatible with arrays with repeated elements.

const areArraysEquivalent = <T extends string | number | symbol>(
  a: T[],
  b: T[]
): boolean => {
  const keysAppears: Record<T, number> = {} as Record<T, number>

  for (const key of a) {
    keysAppears[key] = keysAppears[key] ? (keysAppears[key] as number) + 1 : 1
  }

  for (const key of b) {
    if (!keysAppears[key]) {
      return false
    }
    keysAppears[key] = (keysAppears[key] as number) - 1
  }

  return Object.values(keysAppears).every(value => value === 0)
}

• ✅ Complexity of N+M
• ✅ Compatible with repeated elements
• ⚠️ Order insensitive
• ❗ Only compatible with types that can be indexes (number | string | symbol)

Playground link

Graehl

Answer 4

The best way to do this is to convert the arrays to sets. The repo: https://github.com/bn-l/ProposalSet has efficient implementations for all the proposed set methods (with progressive fall-back to the native implementation if it exists) with links to MSDN docs (note: I am the author).

E.g.:

import pSet from "proposal-set";

const setX = new pSet([1, 2, 3]);
const setY = new pSet([1, 2]);

console.log(setX.difference(setY));
// => Set(1) { 3 }

Then to go back to an array (if you want, members in the set can also be accessed):

Array.from(setX);

Set methods are very fast and the api is simple. No need to reinvent the wheel here.

Combe