How to avoid for loop inside for loop in javascript

Question

I've written a piece of code that works fine. I want a new array consisting of the elements from myArr in the order specified in orderArr. However, it uses for loop inside another for loop to match array elements.

var myArr = ['a', 'b', 'c', 'd', 'e'];
var orderArr = ['e', 'c'];
var reArr = [];

for (var i = 0; i < orderArr.length; i++) {
  for (var k = 0; k < myArr.length; k++) {
    if (myArr[k] == orderArr[i]) {
      reArr.push(myArr[k]);
    }
  }
}

console.log(reArr);

I've often heard that using for loops inside another for loop is bad practice and even forEach should be avoided.

How else can I re-write this code.

Solution 1

I wouldn't necessarily say that using loops inside loops is a bad practice -- in fact Ori Drori beat me to stating that the efficiency of such a practice might simply depend on the size of the data set.

For example, there are many implementations of sorting algorithms and you'll often find loops within loops. However the details of the implementation impact the performance as the data sizes change.

My own personal experience is that when I see nested loops I immediately ask myself if the operation it's performing needs to be optimized with a different algorithm. More often than not in JavaScript (browser) applications the answer is "no" because data sizes are rarely big enough to make an impactful difference.

Solution 2

The complexity of having nested loops in your case is O(n * m) - n the length of orderArr, and m the length of myArr.

This solution complexity is O(n + m) because we're creating the dictionary object using Array#reduce with complexity of O(m), and then filtering the orderArray with a complexity of O(n).

Note1: For small arrays, this shouldn't really matter. So unless you've got a few thousands in both array, you can stay with the nested loops.

Note2: This code assumes that there are no duplicates in myArr. If there are duplicates, the result will differ from that of the nested loops.

var myArr = ['a', 'b', 'c', 'd', 'e'];
var orderArr = ['e', 'c'];
var myArrDict = myArr.reduce(function(r, s) {
  r[s] = true;
  return r;
}, Object.create(null));

var reArr = orderArr.filter(function(s) {
  return this[s];
}, myArrDict);

console.log(reArr);

Solution 3

I don't think there is anything wrong with your code but if you really want to you can eliminate the (visible to you) loops with this:

var reArr = myArr.filter((n) => orderArr.includes(n));

(Will not work in old versions of IE).

Solution 4

What you can do is combine the two arrays and remove everything but the duplicates using reduce like so:

var myArr = ['a', 'b', 'c', 'd', 'e'];
var orderArr = ['e', 'c'];
// Merge the two arrays
var reArr = myArr.concat(orderArr);

let result = reArr.reduce((arr, val) => {
  // return only equal values that are not already in the new array
  // If the value is in the new array 'indexOf()' will be greater than -1
  // we will then not modify the current array
  //
  // If the value is not in the new array and is equal to the current lookup 
  // then add it to the filter. Once filtered, we can check
  // if the filter contains more than one item if it does
  // then we can add it to the new array
  return reArr.filter(v => v == val && arr.indexOf(val) == -1).length > 1 
    // If it is not in the new array add it using 'concat()'
    // otherwise we will return the current array as is
    ? arr.concat(val) : arr
}, [])

console.log(result);

Solution 5

Personally, I like to have a dedicated correlate function for this particular scenario.

"use strict";

function correlate(
  outer,
  inner, 
  outerKeyOrKeySelector = x => x,
  innerKeyOrKeySelector = x => x
) {
  const outerValues = [...outer];
  const innerValues = [...inner];
  const outerToKey = typeof outerKeyOrKeySelector === 'function'
      ? outerKeyOrKeySelector
      : (x => x[outerKeyOrKeySelector]);

  const innerToKey = typeof innerKeyOrKeySelector === 'function'
      ? innerKeyOrKeySelector
      : (x => x[innerKeyOrKeySelector]);

  const outerKeyed = outerValues.map(value => ({key: outerToKey(value), value});
  const innerKeyed = innerValues.map(value => ({key: innerToKey(value), value});

  return outerKeyed.reduce((results, {key: oKey, value: oValue}) => [
     ...results,
     ...innerKeyed
         .filter(({key: iKey}) => oKey === iKey)
         .map(({value: iValue}) => [oValue, iValue])
    ], []);
}

This basically acts like a JOIN and allows you to correlate two arrays based on either the value of a property or an arbitrary projection function.

It may seem like overkill, and YMMV, but I find it very useful.

Applied to the problem at hand:

reArr = correlate(orderArr, myArr).map(([first, second]) => first);

But it handles complex scenarios just as easily

reArr = correlate(orders, customers, o => o.customer.name, c => c.name)
  .map(([first, second]) => {order: first, customer: second})
  .forEach(({customer, order}) => {
    customer.orders = [...customer.orders, order];
  });

View more solutions

Comments

[Jaromanda X]

Will not work in old versions of IE unless you use polyfills for filter/includes methods

[SBFrancies]

A problem with this approach is that it won't preserve duplicates from the original array in the returned array (which the looping code does).

[Ori Drori]

@SBFrancies - that's a good point, which I haven't considered. I'll add a note.

[Romain Vincent]

did you even test your piece of code? Syntax error in it. And humongous error in usage of map.

[bhantol]

@RomainVincent - fixed the code snippet. You were right. there were several problems