24

假设我有一个巨大的（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：是的，我想在客户端进行过滤，因为我想提供“离线功能”。

4

5 回答 5

19

根据经验，以下算法效果很好：

  1. 当用户键入第一个字母时，您使用也许执行搜索Array.filter()并将该结果存储在用户键入的任何内容下（例如“j”）；

  2. 当用户键入另一个字母（例如“o”）时，您对之前键入的任何内容（“j”）执行搜索，从而减少要通过的项目数

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

于 2012-11-26T13:37:02.947 回答
9

尽管子字符串索引（例如Suffix tree）会使这更快，但直接搜索将是：

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

wheres是查询字符串，l是对象列表。

于 2012-11-26T13:35:47.600 回答
4

在这种情况下，我不会太担心性能。一台台式计算机应该吃掉 1000 次或 10,000 次评估而不会出汗。我会避免任何类型的复杂优化，因为破坏功能的风险可能高于稍微高效处理的好处。

Javascript (ECMAScript 5) 确实提供了过滤数组的新方法。作为本机方法，它应该更快一些。

var regex = ...

results = json.filter(function(result) {
   return regex.test(result.name)
}

现代浏览器支持 Array.prototype.filter，请参阅http://kangax.github.com/es5-compat-table/。可以添加旧浏览器的补丁：https ://github.com/kriskowal/es5-shim

于 2012-11-26T13:42:50.770 回答
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/

于 2021-04-11T18:00:20.107 回答
1

从简单到更复杂（没有额外的库）：

  1. 限制搜索最小 x 字符（通常 3 是可以接受的）
  2. 在用户使用超时输入时延迟过滤：
//clear previous timed filtering
if (typingTimeout) {
      clearTimeout(typingTimeout);
      typingTimeout = null;
    }
//schedule new filtering
typingTimeout = setTimeout(() => {
   // do some filtering
}, 2000); //acceptable 1-2s
  1. 如果您仍然希望更快地过滤，您可以按字母顺序将列表分组到一个对象中：
{
   A: ['Aron', 'Arnold', ...],
   B: ['Baby'],
   ....
}

然后使用输入第一个字符的前缀列表过滤它们。这只是一个示例，您应该按照您认为合适的方式对数据进行分组（可能是前 2 个字母......）。

这是我实现的一个函数来帮助为我的数组添加前缀：

export function prefixStringsArray(arr, prefixLength) {
  const prefixArr = arr.map((s) => s.substr(0, prefixLength));
  const filter = (item, query) =>
    item.toLowerCase().startsWith(query.toLowerCase());

  const prefixObj = {};
  for (const pre of prefixArr) {
    prefixObj[pre] = arr.filter((item) => filter(item, pre));
  }

  return prefixObj;
}

你应该知道使用 JS 对象是一个很好的选择，因为它们是在 O(1) 中访问的（它是一种哈希映射），如果你对数据进行最佳分组，你会得到小数组来过滤。

笔记：

  1. 如果您选择为数组添加前缀，则应注意用户搜索query.length < prefixLength
  2. 这给了我在移动开发（React Native）方面的巨大成果
  3. 代码只是草稿 - 手动测试
于 2020-08-12T15:06:13.017 回答