How to find first n array items that match a condition without looping through entire array

Question

I am trying to find the first 100 items in a very large array that match a condition and I'd prefer to end the loop once I've found those 100 for efficiency sake, since the method for matching the items is expensive.

The problem is that doing:

const results = largeArray.filter(item => checkItemValidity(item)).slice(0, 100);

will find all the results in the large array before returning the first 100, which is too wasteful for me.

And doing this:

const results = largeArray.slice(0, 100).filter(item => checkItemValidity(item));

could return less than 100 results.

Please what's the most efficient way of doing this?

You could add a counter to your javascript. Every time it finds an item fitting your conditions, add +1 to the counter. Then once the counter reaches 100, stop the loop. — kvncnls, Aug 08 '20 at 16:21
Not an exact duplicate but the general idea is to break from array methods: [Short circuit Array.forEach like calling break](https://stackoverflow.com/questions/2641347) — adiga, Aug 08 '20 at 16:26

score 8 · Accepted Answer · answered Aug 08 '20 at 17:10

Rather than putting a conditional and break inside a for loop, just add the extra length check in the for condition itself

const data = ["1", "2", "3", "4", "5", "6", "7", "8", "9", "10", "11", "12", "13", "14"],
      isValid = n => !(n%2),
      res = [],
      max = 5;

for (let i = 0; i < data.length && res.length < max; i++) {
   isValid(data[i]) && res.push(data[i]);
}

console.log(res)

score 3 · Answer 2 · answered Aug 08 '20 at 16:41

There are several array methods that will exit early Array.some, Array.every, Array.find, Array.findIndex

You can use them to stop the iteration when you need.

Example using Array.find

const data = [-1,-6,-6,-6,1,-2,2,3,4,-5,5,6,7,-8,8,9,-10,10,11,-1,2,3,4,5,-6,7,8,-9,10,11,];
const first10 = [];

data.find(item => (item > 0 && first10.push(item), first10.length >= 10));

console.log(first10 +"");

score 2 · Answer 3 · answered Aug 08 '20 at 16:42

You ocul take a generator function and exit of the wanted length is found.

function* getFirst(array, fn, n) {
    let i = 0;
    while (i < array.length) {
        if (fn(array[i])) {
            yield array[i];
            if (!--n) return;
        }
        i++;
    }
}
const
    expFn = x => x % 2 === 0,
    array = [2, 4, 5, 1, 3, 7, 9, 10, 6, 0];
    
console.log(...getFirst(array, expFn, 4));

score 1 · Answer 4 · answered Aug 08 '20 at 16:28

The most efficient way would be to use a for construct instead of a function and then break out when you have reached your limit.

const results = []
for (const item of largeArray) {
  // End the loop
  if(results.length === 100) break

  // Add items to the results
  checkItemValidity(item) && results.push(item)
} 

console.log(results)

Pramod Mali · Answer 5 · 2020-08-08T16:35:37.697

1

You can use something like this. I.e. Finding the first 5 odd numbers

var data = ["1", "2", "3", "4", "5", "6", "7", "8", "9", "10", "11", "12", "13", "14"]

var filterData = [];
for (let i = 0; i < data.length; i++) {
  if (data[i] % 2 === 0) {
    filterData.push(data[i]);
  }
  // Track count  console.log(i)
  if (filterData.length === 5)
    break;
}

console.log(filterData)

edited Aug 08 '20 at 16:35

answered Aug 08 '20 at 16:29

Pramod Mali

1,588
1
17
29

1

Why `>=` instead of just `==`? Once it `break`s, it will never come there again. – adiga Aug 08 '20 at 16:33
1

Yeah, that also works! just personal preference. Updated to use safer === – Pramod Mali Aug 08 '20 at 16:35

score 1 · Answer 6 · answered Aug 08 '20 at 16:38

You would need to do a standard "for" loop as filter function returns a new array of the given array so here is how I would approach this:

let largeArray = ["foo", "bar", "foo", "bar"]
let validateArray = ["foo"]
let newArray = []
for (let item of largeArray){
    //change number to how many items needed
    if (newArray.length === 2){
       console.log(newArray)
       // Output would be ["foo", "foo"]
       break;
    }
    // If you have a custom function to return true or false replace here
    if (validateArray.includes(item)){
        newArray.push(item);
    }
}

If you are not returning strings you might need to create a custom function to return true or false depending on how you would define a validate data

score 1 · Answer 7 · answered Oct 25 '22 at 07:09

1

I'll recommend you use findIndex, the problem with the some and every is that if the array is empty it will return true

Reference: Why does Array.prototype.every return true on an empty array?

answered Oct 25 '22 at 07:09

Alfrex92

6,278
9
31
51

score 0 · Answer 8 · edited Aug 08 '20 at 16:39

0

I'm going to assume that what is expensive is the function that you are using to filter items in the array, not the actual iteration.

In that case, I would recommend using the array objects .reduce() method. Inside the function you pass to it, you can check whether your accumulator is already large enough. If it isn't, then you can conditionally add to it.

const results = largeArray.reduce(( accumulator , item )=> {
  if (accumulator.length <= 100) {
    if (checkItemValidity(item)) {
      accumulator.push(item)
    }
  }
  return accumulator
}, [])

edited Aug 08 '20 at 16:39

Dharman

30,962
25
85
135

answered Aug 08 '20 at 16:33

JuanCaicedo

3,132
2
14
36

1

It will still gonna loop till `array.length` as you are just checking for the insert condition – Shubham Dixit Aug 08 '20 at 17:15
@Shubh Yeah that's a good point that's why I called it out in the first line of my answer – JuanCaicedo Aug 08 '20 at 18:17

How to find first n array items that match a condition without looping through entire array

8 Answers8