Javascript/lodash 过滤数组非常慢

Question

我有一大堆对象。我正在根据该对象的一个​​属性过滤第一个数组来创建第二个数组。我的代码是...

let re = RegExp("^" + term, "i");
this.filteredList = _.filter(this.list, item => item.value.search(re) > -1);

哦...我现在正在使用 lodash，但 native Javascript 过滤器也同样慢。有没有更有效的方法来过滤数组？

Answer 1

我将在这里反对并说你不会比正则表达式做得更好，并且我有基准来支持它。

我不会谈论 lodash，lodash 不会做任何会极大改变性能特征的事情。

TL;DR

您可以通过将 item.value.search(re) > -1 替换为 re.test(item.value) 来提高性能。您会得到相同的结果，但工作量会少一些。有了这个(并且没有 lodash)，您的代码如下所示:

let re = RegExp('^' + term, 'i');
this.filteredList = this.list.filter(item => re.test(item.value));

...这就是您能做到的最好的了。

基准

我尝试了四种不同的方法:

1. toLowerCase().startsWith，即acontell's (original) solution :

   var termLower = term.toLowerCase();
   var filteredList = list.filter(
     item => item.toLowerCase().startsWith(termLower));
   

2. slice().toLowerCase 相等，即 trincot's solution :

   var termLower = term.toLowerCase();
   var filteredList = list.filter(
     item => item.substr(0, termLower.length).toLowerCase() === termLower);
   

3. RegExp#test(获胜者):

   var expr = new RegExp('^' + term, 'i');
   var filteredList = list.filter(item => expr.test(item));
   

4. String#search(您的原始解决方案):

   var expr = new RegExp('^' + term, 'i');
   var filteredList = list.filter(item => item.search(expr));
   

您可以在这里查看我的基准:https://jsperf.com/array-of-strings-prefix-search#10 。请注意 URL 末尾的 #10。更改数字即可更改 list 中字符串的长度(以单词为单位)。设置代码构建一个包含 100 个给定长度的句子的数组 (searchSpace) 和一个包含 100 个搜索前缀的数组。

我在 Chrome 64 (macOS 10.12) 中运行了句子长度从 1 到 500 的基准测试。结果如下:

不出所料，句子越长，toLowerCase().startsWith 的性能就会逐渐变差，因为它每次都必须将整个句子小写。

同样，slice().toLowerCase equals 在 1 和 2 之间下降后保持不变，因为无论如何它都只小写一个单词。

然后是 RegExp#test 和 String#search，它们基​​本上做同样的事情，除了后者需要做少量的额外工作。现代 JavaScript 引擎非常擅长编译正则表达式，尤其是像 /^keyword/ 这样非常简单的表达式。最后，使用正则表达式搜索要快得多，因为我们不必进行任何小写或切片。

后记

每个基准都是有限的，而且我的基准也完全有可能在某些方面存在重大缺陷。我很高兴听到任何关于如何改进它的想法。