如何加快数组搜索功能？

Question

我正在写字典应用程序，用react本地语言编写。

当我想从搜索框中过滤数组时，我编写了下面的函数。这是相当好的工作，当我测试2000字表。但是，当单词列表到达数千个时，搜索速度确实很慢。

那么，我如何改进这个搜索功能呢？

//Filter array when input text (Search)

let filteredWords = []
if(this.state.searchField != null)
{
  filteredWords = this.state.glossaries.filter(glossary => {
    return glossary.word.toLowerCase().includes(this.state.searchField.toLowerCase());
  })
}

Answer 1

由于不会似乎属于CodeReview的问题，我认为您可以做一些事情来使代码更快地被引用。

• 缓存对this.state.searchField.toLowerCase()的调用，因为您不需要在每次迭代中调用它。
• 使用常规的旧for循环，而不是浮华但缓慢的Array函数。

这是最后的结果：

let filteredWords = []
if(this.state.searchField != null) {
    let searchField = this.state.searchField.toLowerCase(),
        theArray = this.state.glossaries;                          // cache this too

    for(let i = 0, l = theArray.length; i < l; ++i) {
        if(theArray[i].word.toLowerCase().includes(searchField)) {
            filteredWords.push(theArray[i]);
        }
    }
}

编辑：

如果要搜索其word以searchField开头的术语表，请使用indexOf === 0而不是includes作为如下条件：

if(theArray[i].word.toLowerCase().indexOf(searchField) === 0) {

Answer 2

有多个因素使这段代码变慢：

• 你用的是filter()和lambda。这将为搜索的每个项增加一个函数调用开销。
• 在调用toLowercase()之前，在两个字符串上调用includes()。这将为每个比较分配两个新的字符串对象。
• 你给includes打电话。由于某些原因，includes()方法在某些浏览器中没有indexOf()更好地优化。

for循环(-11%)

我建议不要使用filter()方法，而是创建一个新的Array，并使用一个for循环来填充它。

const glossaries = this.state.glossaries;
const searchField = this.state.searchField;
const filteredWords = [];   

for (let i = 0; i < glossaries.length; i++) {
  if (glossaries[i].toLowerCase().includes(searchField.toLowerCase())) {
    filteredWords.push(glossaries[i]);
  }
}

toLowerCase拨款(-45%)

内存分配非常昂贵，因为JavaScript使用垃圾收集机制来释放使用过的内存。当执行垃圾回收时，整个程序会暂停，同时尝试查找不再使用的内存。

您可以完全摆脱toLowerCase() (在搜索循环中)，每次更新术语表时都要复制术语表，我认为这种情况并不常见。

// When you build the glossary
this.state.glossaries = ...;
this.state.searchGlossaries = this.state.glossaries.map(g => g.toLowerCase());

您还可以在循环之前调用toLowerCase()一次，从而在searchText上删除它。这些更改之后，代码将如下所示：

const glossaries = this.state.glossaries;
const searchGlassaries = this.state.searchGlossaries;
const searchField = this.state.searchField.toLowerCase();
const filteredWords = []; 

for (let i = 0; i < glossaries.length; i++) {
  if (searchGlassaries[i].includes(searchField)) {
    filteredWords.push(glossaries[i]);
  }
}

indexOf()而非includes() (-13%)

我不太清楚为什么会这样，但是测试表明indexOf比includes快得多。

const glossaries = this.state.glossaries;
const searchGlassaries = this.state.searchGlossaries;
const searchField = this.state.searchField.toLowerCase();
const filteredWords = []; 

for (let i = 0; i < glossaries.length; i++) {
  if (searchGlassaries[i].indexOf(searchField) !== -1) {
    filteredWords.push(glossaries[i]);
  }
}

总的来说，性能提高了70%。我从https://jsperf.com/so-question-perf那里得到了性能百分比

优化算法

在注释中，您说您想要一个优化的例子，当需求被放松为只匹配以搜索文本开头的单词时，可以进行优化。这样做的一种方法是一个二进制搜索。

让我们以上面的代码为起点。在将术语表存储到州之前，我们对其进行排序。为了不敏感地排序大小写，JavaScript公开了Intl.Collator构造函数。它提供了返回以下内容的compare(x, y)方法：

negative value  | X is less than Y
zero            | X is equal to Y
positive value  | X is greater than Y

以及由此产生的代码：

// Static in the file
const collator = new Intl.Collator(undefined, {
  sensitivity: 'base'
});

function binarySearch(glossaries, searchText) {
  let lo = 0;
  let hi = glossaries.length - 1;

  while (lo <= hi) {
    let mid = (lo + hi) / 2 | 0;
    let comparison = collator.compare(glossaries[mid].word, searchText);

    if (comparison < 0) {
      lo = mid + 1;
    }
    else if (comparison > 0) {
      hi = mid - 1;
    }
    else {
      return mid;
    }
  }

  return -1;
}

// When you build the glossary
this.state.glossaries = ...;
this.state.glossaries.sort(function(x, y) {
  return collator.compare(x.word, y.word);
});

// When you search
const glossaries = this.state.glossaries;
const searchField = this.state.searchField.toLowerCase();
const filteredWords = [];

const idx = binarySearch(glossaries, searchField);

if (idx != -1) {
  // Find the index of the first matching word, seeing as the binary search
  // will end up somewhere in the middle
  while (idx >= 0 && collator.compare(glossaries[idx].word, searchField) < 0) {
    idx--;
  }

  // Add each matching word to the filteredWords
  while (idx < glossaries.length && collator.compare(glossaries[idx].word, searchField) == 0) {
    filteredWords.push(glossaries[idx]);
  }
}