代码之家 › 专栏 › 技术社区 › Andrew Cooper

Javascript/lodash过滤数组的速度非常慢

lodash regex javascript

Andrew Cooper · 技术社区 · 8 年前

我有一个很大的物体阵列。我正在创建第二个数组,根据该对象的一个属性过滤第一个数组。我的代码是。。。

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

哦目前我正在使用lodash,但原生Javascript过滤器的速度同样慢。是否有更有效的方法来过滤阵列?

3 回复 | 直到 8 年前

Jordan Running 8 年前

我将在这里做一个相反的人,说你不会比正则表达式做得更好,我有基准来支持它。

我不会谈论lodash,lodash并没有做任何会大大改变性能特征的事情。

TL;博士

您可以通过交换 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));

...这大概是你能做的最好的了。

基准

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

toLowerCase()。开始使用 ,即。 acontell's (original) solution :

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

切片()。toLowerCase相等 ,即。 trincot's solution :

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

RegExp#测试 (获胜者):

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

字符串#搜索 (您的原始解决方案):

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

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

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

毫不奇怪, toLowerCase()。开始使用 句子越长,情况越糟,因为每次都必须将整个句子小写。

同样地 切片()。toLowerCase相等 它在1到2之间下降后保持不变,因为不管发生什么,它只会小写一个单词。

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

后记

每个基准都是有限的,我的也完全有可能在某些重要方面存在缺陷。我很乐意听到关于如何改进它的任何想法。

trincot 8 年前

速度减慢肯定是由正则表达式引起的。尝试不使用它:

const termL = term.toLowerCase();
this.filteredList = this.list.filter(
    item => item.substr(0, termL.length).toLowerCase() === termL
);

acontell 8 年前

如果要检查字符串是否以术语开头(不区分大小写),可以使用lodash _.startsWith 并避免使用regexp。

尽管基准测试并不完美,但它可以让您了解一些答案的性能。

const list = [...Array(10000).keys()].map(n => 'asdfAasdfaSSSddd');
const term = 'd';

console.time('original');
let re = RegExp("^" + term, "i");
_.filter(list, item => item.search(re) > -1);
console.timeEnd('original');

console.time('one solution with lodash');
let termLowerCase = term.toLowerCase();
_.filter(list, item => item[0].toLowerCase() === term);
console.timeEnd('one solution with lodash');

console.time('another solution with lodash');
let termLowerCase1 = term.toLowerCase();
_.filter(list, item => _.startsWith(item.toLowerCase(), termLowerCase1));
console.timeEnd('another solution with lodash');

console.time('trinkots solution');
const termL = term.toLowerCase();
list.filter(
    item => item.substr(0, termL.length).toLowerCase() === termL
);
console.timeEnd('trinkots solution');

<script src="https://cdn.jsdelivr.net/npm/lodash@4.17.5/lodash.min.js"></script>