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

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

  •  0
  • Andrew Cooper  · 技术社区  · 7 年前

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

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

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

    3 回复  |  直到 7 年前
        1
  •  3
  •   Jordan Running    7 年前

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

    我不会谈论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));
    

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

    基准

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

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

      var termLower = term.toLowerCase();
      var filteredList = list.filter(
        item => item.toLowerCase().startsWith(termLower));
      
    2. 切片()。toLowerCase相等 ,即。 trincot's solution :

      var termLower = term.toLowerCase();
      var filteredList = list.filter(
        item => item.substr(0, termLower.length).toLowerCase() === termLower);
      
    3. RegExp#测试 (获胜者):

      var expr = new RegExp('^' + term, 'i');
      var filteredList = list.filter(item => expr.test(item));
      
    4. 字符串#搜索 (您的原始解决方案):

      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的句子长度基准测试。以下是结果:

    prefix search benchmark results

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

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

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

    后记

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

        2
  •  3
  •   trincot Jakube    7 年前

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

    const termL = term.toLowerCase();
    this.filteredList = this.list.filter(
        item => item.substr(0, termL.length).toLowerCase() === termL
    );
    
        3
  •  1
  •   acontell    7 年前

    如果要检查字符串是否以术语开头(不区分大小写),可以使用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>