DEV Community

Iterating on an array: should you loop with .map, .forEach or for?

Robin Lejeune on January 31, 2023

TL;DR? Check at least the sections "Time for the comparisons!" and "But wait! There's more" ;) Table of Contents 1. The Problem 2. Ho...
Read full post
Collapse
 
cicirello profile image
Vincent A. Cicirello •

There's another potential optimization that may have a meaningful impact. If there can be a large number of duplicates then your pairs may grow large creating unnecessary overhead. Instead of forming the Set at the end, try initializing an empty Set before your loops, and then instead of adding to pairs, add directly to the set.

Yet another optimization, even more substantial, would be to generate a Set of the numbers in the original array so that you condense it to the unique integers that it contains. Then iterate over the unique integers x in that Set, compute y=target-x, and check if the Set contains y. A lookup in a Set is constant time. In this way, you'd need 1 linear pass over the original array, followed by 1 linear pass over the unique integers. You'd end up with a linear time solution instead of your current quadratic time solution.

Collapse
 
robinlej profile image
Robin Lejeune • • Edited

Oh thanks!
Your first suggestion is painfully obvious, I'm a bit ashamed I did not see it. ^^' Although after a closer look, with an array of 20000 (10000 duplicated), it's actually sliiiightly slower (~ +50 ms, whatever the method). I also tried with an array of 10 replicated 2000 times, with the same result. Maybe it starts having effects well beyond those measures? [Edit: nope, doesn't seem to be the case. With 200,000 items and a for loop, it's several seconds slower to initiate pairs as a Set.]

Anyway, I really didn't think about your second suggestion, although I tried to find a way to avoid looping inside a loop. For the simple reason that you might have one number twice, which combination is valid ([3, 3] to get 6), so a Set didn't seem to be the solution. But that was silly of me, as there's a simple way to check for this case. With your idea I made this function and tested it:

function combine(arr, target) {
    const set = new Set(arr)
    let pairs = new Set()
    let potentialPairings = new Set()

    set.forEach(e => potentialPairings.add(target - e))

    potentialPairings.forEach(pairing => {
        if (set.has(pairing)) {
            const pair = pairing > (target - pairing) ?  `${target - pairing}, ${pairing}` : `${pairing}, ${target - pairing}`
            pairs.add(pair)
        }
    })

    if (arr.filter(n => n === (target / 2)).length < 2) pairs.delete((`${target / 2}, ${target / 2}`))

    console.log(pairs.size)
}
Enter fullscreen mode Exit fullscreen mode

And this takes a whopping 5 ms to run (with 10000 items duplicated).
I think I'm going to edit my article, thanks. :)

Collapse
 
cicirello profile image
Vincent A. Cicirello • • Edited

You're welcome. I'm guessing that if your original solution got all but a couple of their tests due to time, that they probably had at least one test large enough that you needed to have a linear time solution like this one. They probably weren't concerned with the for vs forEach.