javascript - 我怎样才能加快我的数组搜索功能？

Question

我正在研究用 react-native 编写的字典应用程序。

当我想从搜索框中过滤数组时，我写了下面的函数。当我使用 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

有多种因素导致此代码变慢:

• 您正在使用带有 lambda 的 filter()。这会为每个正在搜索的项目增加一个函数调用开销。
• 在调用 includes() 之前，您在两个字符串上都调用了 toLowercase()。这将为每次比较分配两个新的字符串对象。
• 您正在调用 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());

您还可以通过在循环之前调用一次来删除 searchText 上的 toLowerCase()。进行这些更改后，代码将如下所示:

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 得到了性能百分比

优化算法

在评论中你说你想要一个优化的例子，当要求放宽到只匹配以搜索文本开头的单词时可以进行优化。一种方法是使用 binary search .

让我们以上面的代码为起点。在将词汇表存储在状态之前，我们对词汇表进行排序。为了不区分大小写地排序，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]);
  }
}