在JavaScript中过滤JSON对象列表的最高性能方法是什么？

Question

让我们假设我有一个巨大的(1000+)对象列表,如下所示:

[{name: 'john dow', age: 38, gender:'m'}, {name: 'jane dow', age: 18, gender:'f'}, ..]

我想按名称过滤此列表(明智的字符).

filter('j') => [{name: 'john dow', age: 38, gender:'m'}, {name: 'jane dow', age: 18, gender:'f'}, ..]

filter('jo') => [{name: 'john dow', age: 38, gender:'m'}, ..]

filter('dow') => [{name: 'john dow', age: 38, gender:'m'}, {name: 'jane dow', age: 18, gender:'f'}, ..]

最高性能的方法是什么？RegEx显然是其中一个关键,如果你假设用户通常从一开始就倾向于从名字开始也可能是一个好主意,事先对列表进行排序,但这只会在某些情况下有所帮助.

是否有用于映射过滤器的JavaScript内置函数？我希望这些比JavaScript实现更快.

PS:是的我想在客户端进行过滤,因为我想提供"离线功能".

Answer 1

根据经验,以下算法运行良好:

1. 当用户键入第一个字母时,您可以使用Array.filter()或者执行搜索,并将该结果存储在用户类型的任何内容下(例如"j");

2. 当用户键入另一个字母(例如"o")时,您可以对之前键入的内容("j")执行搜索,从而减少要经过的项目数量

3. 当用户删除一个或多个字符时,您会尝试根据搜索框中剩余的内容查找存储的搜索; 如果全部失败,则显示空列表并使先前存储的搜索无效.

Answer 2

虽然子字符串索引(例如后缀树)会使这更快,但直接搜索将是:

function (s, l) {
    return l.filter(function (v) {
        return v.name.find(s) !== -1;
    });
}

s查询字符串在哪里,是l对象列表.

Answer 3

20000 个随机项目（实时查看过滤 20k 条记录和时间）

let dictionary = [];
  var time=0;
  var answer = [];

  var possible = "abcdefghijklmnopqrstuvwxyz";
  function makeid(len) {
    var text = "";


    for (var i = 0; i < len; i++)
      text += possible.charAt(Math.floor(Math.random() * possible.length));

    return text;
  }

  function addWord(number){
    for (var inc=0; inc<number; inc++){
      var wl = 5+Math.floor(Math.random() * 5);
      dictionary.push({word:makeid(wl)});
    }
  }

  function findWord(start){
    return dictionary.filter(function(e){
      return e.word.startsWith(start);
    })
  }


  $(document).ready(function( $ ) {

    addWord(20000);
    $("#time").text( 'Search from ' + dictionary.length + ' random items!' );

    $("#search-input").keyup(function() {
      var term = $(this).val() || '';
      

      if( term ) {

        var init = new Date().getTime();
        var sol = findWord( term );
        time= (new Date()).getTime() - init;
        
        console.log( term );
        $("#answer").text(JSON.stringify(sol));
        $("#time").text( sol.length + ' items found in time ' + time + 'ms' );
      } else {
        $("#answer").text(JSON.stringify(dictionary));
        $("#time").text( 'Search from ' + dictionary.length + ' items' );
      }

    });
  });

<script src="https://cdnjs.cloudflare.com/ajax/libs/jquery/3.3.1/jquery.min.js"></script>
<input id="search-input" placeholder="Search..">
<p id="time"></p>
<p id="answer"></p>

https://jsfiddle.net/maheshwaghmare/cfx3p40v/3/