Javascript: Multiple Array looping

Question

TL DR; What is the most efficient way to sort and compare values in a multiple arrays?

Okay, so we'll assume a few constants to make this whole thing simple var a = [1, 2, 3, 4, 5, 6], b = [0, 9, 8, 7, 6, 88, 99, 77], i, j;

Now if I wanted to see if any value in a is equal to any other value in b I'd have to sort through one of these arrays 6 times. That's a lot of work, and it would seem there should be a more efficient way to do this. For those needing a visual aide here you are ( and yes I know about -- and ++ I just don't like to use 'em ):

for (i = a.length - 1; i > -1; i -= 1) {
    for (j = b.length - 1; j > -1; j -= 1) {
        if (a[i] === b[j]) {
            return b[j];
        }
    }
}

The B array gets ran through once for EACH element in A. Again, certainly there is a more efficient way to complete this task?

-Akidi

Answer 1

Depends on the size of your input arrays (several tradeoffs there)-- your nested loops are simplest for small inputs like your examples.

If you have huge arrays, and have control over their construction, consider keeping a map (Object in JS) around acting as a lookup set (if you're creating a in a loop anyways, you can build the set in parallel.)

var setA = {};
for (int i = 0; i < a.length; i++) {
    setA[a[i]] = true;
}

Then you can see whether something exists in the set by just checking setA[?].

Likewise with B, or with both together, etc, depending on your needs.

Answer 2

Maybe something like this may help?

var a = [1, 2, 3, 9, 5, 0], b = [0, 9, 8, 7, 6, 88, 99, 77];
var a_dict = {}, l = a.length;

for (var i=0; i < l; i++) {
  a_dict[a[i]] = 1;
}

l = b.length;
for (var i=0; i < l; i++) {
  if(!!a_dict[b[i]]){
    console.log(b[i]);
  }
}

You can convert one array to "dict-like" object and compare others with it...