JS: Most efficient way to filter results by iterating?

Question

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

Assuming ‘data’ does not change often: transform data to a structure like ‘searchable_name ->[name]’, lowercase and sort it. (This is done once). Now on each search, use binary search on the keys of the map (searchable_name) to get the value (array of names) you’re interested in. This is done in O(log(n)) — Geert-Jan, Oct 27 '19 at 23:43
You can avoid the second foreach with a little trick (that's why this is not an answer). `if( name.searchable_names.join("|").toLowerCase().includes(searchBar.text.toLowerCase())` — Luca Rainone, Oct 27 '19 at 23:54
@LucaRainone what exactly is that doing there? I don't get how that would work — hectoraloneo, Oct 27 '19 at 23:55
@hectoraloneo instead of search into an array, you will search inside a string.It has some limitation, but it could be acceptable in some cases. — Luca Rainone, Oct 28 '19 at 00:00
@LucaRainone - But it would still be almost the same time complexity as second `forEach()` because `join()` requires visiting each array item to form the string, and instead of searching each array item we would be searching the concatenated string. By using `break;` we could avoid visiting rest of the elements when we find a match. Nice trick though! — Nikhil, Oct 28 '19 at 00:05

Nikhil · Accepted Answer · 2019-10-28T00:14:55.950

1

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

edited Oct 28 '19 at 00:14

answered Oct 27 '19 at 23:37

Nikhil

6,493
10
31
68

thanks Nikhil! Just curious: you mention that the #2 approach gives the same time complexity of using `break`; with for loops. So how does a normal nested loop like I have (without breaks) compare to the efficiency of filter() and map() ? Are they implementing a break in their native code? – hectoraloneo Oct 27 '19 at 23:46
@hectoraloneo - `filter()` and `map()` wouldn't use break, but `some()` does — when at least one item in `searchable_names` array matches, it breaks and doesn't continue further searching that array. This is essentially the same as using `break;` with a for loop. – Nikhil Oct 27 '19 at 23:49
@hectoraloneo - No problem. For using `break;` you have to use a regular `for` loop instead of `forEach()` because `break;` isn't available in `forEach()`. More info in this [answer](https://stackoverflow.com/a/2641374/2924577). – Nikhil Oct 27 '19 at 23:56

Edin Omeragic · Answer 2 · 2019-10-28T00:06:22.990

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

score 0 · Answer 3 · answered Oct 27 '19 at 23:32

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

JS: Most efficient way to filter results by iterating?

3 Answers3