CODEWITHSUNDEEP
javascript
hectoraloneo
hectoraloneo

Reputation: 97

JS: Most efficient way to filter results by iterating?

I have a variable called data and have it defined to a list like this: 

[
  {
    name: "Richard", 
    searchable_names:["rich", "dick", "richard", "richie"]
  },
  {
    name: "Anthony", 
    searchable_names:["tony", "anthony"]
  },
]

Using onKeyUp in the search bar, I am trying to filter the results into a new array and display those like this but I realize this is an O(N^2) nested loop and not the most efficient way of doing it. What is a better way for me to resolve this inefficiency:

data.forEach(name => {
    name.searchable_names.forEach(x => {
        if (x.toLowerCase().includes(searchBar.text.toLowerCase())) {
            arr.push(name);
        }
    })
})

Upvotes: 2

Views: 85

Answers (3)

Nikhil
Nikhil

Reputation: 6641

Having nested for loops doesn't always mean the time complexity is O(n^2).

In your code, you are visiting each array item and its searchable_names array only once, so the time complexity is O(n * m).

To improve efficiency:

1) You could use a regular for loop instead of inner forEach() and break when you find a searchable name. This way you wouldn't have to continue searching the inner searchable_names array when you already find a match.

Using regular for loop because there's no built-in ability to break in forEach().

2) Or instead of nested for loops, you could use filter(), some(), and map() methods. This approach gives almost the same time complexity of using break; with for loops.

let arr = data.filter(item => 
  item.searchable_names.some(
    x => x.toLowerCase().includes(searchBar.text.toLowerCase())
  )
).map(item => item.name);

Upvotes: 1

Edin Omeragic
Edin Omeragic

Reputation: 1968

For smaller list let say up to 100.000 strings that should work just fine. To keep things simple things you can do is to move toLowerCase out of loop and use filter and find functions.

var data = [
  {
    name: "Richard", 
    searchable_names:["rich", "dick", "richard", "richie"]
  },
  {
    name: "Anthony", 
    searchable_names:["tony", "anthony"]
  },
]

function filterData(data, value) {
    const valueLowerCase = value.toLowerCase();
    return data.filter(item => {
      return item.searchable_names.find(
        x => x.toLowerCase().includes(valueLowerCase)
      )
    })
}

const result = filterData(data, "a");
console.log(result);

Upvotes: 0

Joelgullander
Joelgullander

Reputation: 1684

You can use array.Filter()

const data = [
  {
    name: "Richard", 
    searchable_names:["rich", "dick", "richard", "richie"]
  },
  {
    name: "Anthony", 
    searchable_names:["tony", "anthony"]
  },
]


function searchName(key) {
  return data.filter(x => 
    x.searchable_names.some(n => n.includes(key.toLowerCase()))
  )
}

console.log(searchName("ri"));

Upvotes: 0

Related Questions