Which looooop? [Part 1]

There are numerous ways in which we can iterate over an appropriate data structure in JavaScript. Examples:

• for

• while

• do...while

• for...of

• for...in

• Array.prototype.forEach

• Array.prototype.map

Time Complexity: All of these ways have a O(n) time complexity

Space Complexity: All of these methods do not use additional space except Array.prototype.map (which uses extra space for returning a new array)

Which method should we use?

Which one is the most performant? [even if they all are of the order of O(n)]

Which one comes with a trade-off?

Before we dive deep into it, let's first settle on our sample size of data and the reasoning behind it!

Setting the iterative stage: Iterating the simple iterables (Arrays)

Check out the below code to see how I am iterating arrays and keeping the behaviour consistent, i.e., all the functions support a callback, which is called with element and index as parameters.

const noop = () => {};

interface ArrayLoopCallback<T = any> {
  (element: T, index?: number): void;
}

interface ArrayLoopFunction {
  <T = any>(arr: T[], callback?: ArrayLoopCallback<T>): void;
}

export const forLoop: ArrayLoopFunction = (arr, callback = noop) => {
  let i = 0;
  for (; i < arr.length; i++) {
    callback(arr[i], i);
  }
};

export const whileLoop: ArrayLoopFunction = (arr, callback = noop) => {
  let i = 0;
  while (i < arr.length) {
    callback(arr[i], i);
    i++;
  }
};

export const doWhileLoop: ArrayLoopFunction = (arr, callback = noop) => {
  // should return if array is empty, otherwise the callback will be called with `undefined` as element
  let i = 0;
  do {
    callback(arr[i], i);
    i++;
  } while (i < arr.length);
};

export const forOfLoop: ArrayLoopFunction = (arr, callback = noop) => {
  let c = 0;
  for (const element of arr) {
    callback(element, c);
    c++;
  }
};

export const forEachMethod: ArrayLoopFunction = (arr, callback = noop) => {
  arr.forEach(callback);
};

export const mapMethod: ArrayLoopFunction = (arr, callback = noop) => {
  arr.map(callback);
};

Now... the moment of truth! * drumrolls *

1. Small sample size (array length between 50 & 2,500)

   

2. Medium sample size (array length between 5,000 & 50,000)

   

3. Large sample size (array length between 100,000 & 1,000,000)

   

Applying the iteration concepts to problems!

I am assuming we all know JavaScript, because it's like aloo 🥔 (potato – goes with everything). Even if some of us are new, it's just a prompt away (#iykyk)!

Strings (iterables)

Let's solve an easy LeetCode problem and compare the concepts we've seen so far.

LeetCode Question:

• 557. Reverse Words in a String III

Description (copy-pasted):

• Given a string s, reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.

Examples (copy-pasted):

• Let's take LeetCode contest ➡️ s'teL ekat edoCteeL tsetnoc

• Mr Ding ➡️ rM gniD

Solutions:

1.    function reverseWords1(s: string): string {
        return s
          .split(' ')
          .map((w) => w.split('').reverse().join(''))
          .join(' ');
      }
   

   ↗️↗️↗️↗️ The one-liner JavaScript solution! Neat-o!

2.    function reverseWords2(s: string): string {
        let out = '';
        let prev = 0;
        for (let i = 0; i <= s.length; i++) {
          if (s[i] === ' ' || !s[i]) {
            for (let j = i - 1; j >= prev; j--) {
              out += s[j];
            }
            out += s[i] || '';
            prev = i + 1;
          }
        }
        return out;
      }
   

   ↗️↗️↗️↗️ Using the 'for' loop, just a few more lines of code!

3.    function reverseWords3(s: string): string {
        let out = '';
        let prev = 0;
        let i = 0;
        for (const char of s) {
          if (char === ' ') {
            for (let j = i - 1; j >= prev; j--) {
              out += s[j];
            }
            out += char;
            prev = i + 1;
          }
          i++;
        }
        for (let j = i - 1; j >= prev; j--) {
          out += s[j];
        }
        return out;
      }
   

   ↗️↗️↗️↗️ Using the 'for-of' loop, a few more lines of code!

4.    function reverseWords4(s: string): string {
        let out = '';
        let prev = 0;
        let i = 0;
        for (i; i < s.length; i++) {
          if (s[i] === ' ') {
            for (let j = i - 1; j >= prev; j--) {
              out += s[j];
            }
            out += s[i];
            prev = i + 1;
          }
        }
        for (let j = i - 1; j >= prev; j--) {
          out += s[j];
        }
        return out;
      }
   

   ↗️↗️↗️↗️ After replacing the 'for-of' loop with the 'for' loop!

All the solutions work (same output)! But which one is the best? Let's see!

Test case explanation:

• Fixed length of sentence (ex: 100, 500, 1000, etc.)

• One test case is equal to 1 auto-generated sentence of fixed length specified above

• Total 3 test cases

• For each test case (i.e., auto-generated sentence), I executed all the functions (solutions 1 – 4) and compared their benchmark outcomes

• Link to Google Sheet containing information about the performance evaluations

My Take:

1. Memory

   1. In all cases, we are using additional memory [O(n)].

   2. In the first solution, a temporary array needs to be created to store all the words in the sentence, and then for each character of every word in that array. And finally, a new string that has the same length as the input string.

   3. In the rest of the solutions, there is just the new string that holds the output string.

2. Function execution in proportion to input size

   1. map-split-join approach

      1. Unoptimized when dealing with larger data set

   2. for-of-loop approach

      1. Much better than the map-split-join approach

      2. In general, it is not better than the "for" loop (solution 3 vs solution 4)

      3. It may perform somewhat better than the "for" loop due to any unoptimized comparison (solution 3 vs solution 2)

      4. Take a look at the inner loop (for (let j = i - 1; j >= prev; j--) { /* */ }); the for-of-loop could not be used here unless we created a substring

   3. for-loop approach

      1. It might not work optimally if we are doing unoptimized comparisons (solution 2 vs solution 4)

   4. Click here to see test comparisons and relevant numbers

Conclusion:

• We saw when for-of loop outperformed for loop when we did not use it optimally

• The for loop is definitely fastest when used optimally! (solution 2 vs solution 4)

• Drawing on the conclusions from the previous section, I have not used other ways to iterate the string. Would you like to try and compare them yourself?

Objects (enumerables)

Stay tuned for the analysis of JavaScript objects (conceptually, Hash Tables)!

In the next article, we will cover different and optimal ways to iterate a Hash Table in JavaScript.