javascript - JS : Most efficient way to filter results by iterating?

Question

我有一个名为 data 的变量，并将其定义为如下列表:

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

在搜索栏中使用 onKeyUp，我试图将结果过滤到一个新数组中并像这样显示这些结果，但我意识到这是一个 O(N^2) 嵌套循环，而不是最有效的方法。解决这种低效率问题的更好方法是什么:

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

Answer 1

具有嵌套的 for 循环并不总是意味着时间复杂度为 O(n^2)。

在您的代码中，您只访问每个数组项及其 searchable_names 数组一次，因此时间复杂度为 O(n * m)。

提高效率:

1) 您可以使用常规的 for loop而不是内部 forEach() 并在找到可搜索名称时中断。这样，当您已经找到匹配项时，您就不必继续搜索内部 searchable_names 数组。

使用常规 for 循环因为 there's no built-in ability to break in forEach() .

2) 或者您可以使用 filter() 而不是嵌套的 for 循环, some() , 和 map()方法。这种方法的时间复杂度与使用 break; 和 for 循环几乎相同。

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