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?

Answer 1

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)

Answer 2

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 +"");

Answer 3

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));

Answer 4

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)

Answer 5

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)

Answer 6

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