我正在开发一个用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());
})
}
这段代码运行缓慢的原因有多个：
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]);
}
}
由于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]);
}
}
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]);
}
}
}
编辑：
如果您想搜索以 searchField 开头的词汇表，则使用 indexOf === 0 作为条件，而不是使用 includes，代码如下：
if(theArray[i].word.toLowerCase().indexOf(searchField) === 0) {
Array函数（例如filter）与常规的for循环相比速度较慢。如果您想让代码更快，则可以使用for循环进行重构，这并不难做到。 - ibrahim mahririncludes()误读为Array.prototype.includes变体。 - Zeta