CODEWITHSUNDEEP
javascriptarraysperformancefor-loop
Zoe Robertson
Zoe Robertson

Reputation: 3

Checking for matching values in two arrays using for loop, is it faster to iterate through the smaller loop?

I am creating a function that will accept two parameters, which are each arrays, and return a separate array of matching values between the two arrays.
I made two versions of the function,

  1. Defaults to iterate through the first parameter in a for loop, and checks the second parameter for a matching value using .includes()

ex:

var matches = [];
for (let i = 0, len = array1.length; i < len; i++) {
    var a = array1[i];
    if (array2.includes(a)) {
        matches.push(a)
    }
  1. Measures and compares the lengths of the two arrays, and chooses the shorter array to iterate through in the for loop

ex:

if (array1.length <= array2.length) {
    var itArr = array1;
    var checkArr = array2 }
else { var itArr = array2
       var checkArr = array1 };
var matches = [];
for (let i = 0, len = itArr.length; i < len; i++) {
    var a = itArr[i];
    if (checkArr.includes(a)) {
        matches.push(a)
    }

My question is whether or not this actually improves the performance, or makes no difference, or harms the performance (by adding more variable definitions, calculations, etc.)?

Upvotes: 0

Views: 269

Answers (3)

Keith
Keith

Reputation: 24181

Here is an example of using a Set for seeing if one array contains values from the other.

If your not ES6, (and why not?), you could use a simple object literal.

This should be faster than doing a double for loop, as that's kind of what includes would be doing.

function makeRandom(count, max) {
  return Array.from(new Array(count),
    (a,ix) => Math.round(Math.random() * max));
}

function union(a,b) {
  var aSet = new Set(a), oSet = new Set();
  b.forEach((v) => { if(aSet.has(v)) oSet.add(v) });
  return Array.from(oSet);
}


const
  random1 = makeRandom(5, 10),
  random2 = makeRandom(5, 10);
  
const
  unionArray = union(random1, random2);
  
console.log(random1.join(':'));
console.log(random2.join(':'));
console.log(unionArray.join(':'));

Upvotes: 0

Ringuerel
Ringuerel

Reputation: 122

I think I would go for the first approach, due to the .includes function will try to iterate the array and return true when it finds the element, so if the element is in the end of the array it iterates completely on it. Hence your attempt for chosing the small one shouldn't make too much difference.

Upvotes: 0

marvel308
marvel308

Reputation: 10458

It wouldn't make significant difference since the worst case complexity would be O(n*m) where n and m are the length of the arrays.

You can sort the 2 arrays and find the intersection using 2 pointers, The time complexity in that case would be O(nlogn + mlogm + n + m) subject to the sorting algorithm used

Upvotes: 1

Related Questions