通过大型 js 字符串数组优化搜索?

新手上路,请多包涵

如果我有一个包含超过 10,000 个元素的大型 javascript 字符串数组,我该如何快速搜索它?

现在我有一个 javascript 字符串数组,用于存储作业的描述,并且我允许用户在他们输入输入框时动态过滤返回的列表。

所以说我有一个像这样的字符串数组:

var descArr = {"flipping burgers", "pumping gas", "delivering mail"};

并且用户想要搜索: "p"

我如何能够快速搜索其中包含 10000 多个描述的字符串数组?显然我无法对描述数组进行排序,因为它们是描述,所以二分搜索就结束了。由于用户可以通过 "p""pi" 或字母的任意组合进行搜索,因此此部分搜索意味着我不能使用关联数组(即 searchDescArray["pumping gas"] )以加快搜索速度。

有什么想法吗?

原文由 TriFu 发布,翻译遵循 CC BY-SA 4.0 许可协议

阅读 389
2 个回答

由于实际浏览器中的正则表达式引擎在速度方面变得疯狂,那么这样做怎么样?而不是数组传递一个巨大的字符串并用标识符分隔单词。例子:

  • 字符串 "flipping burgers""pumping gas""delivering mail"
  • 正则表达式: "([^"]*ping[^"]*)"

使用开关 /g 对于全局,您可以获得所有匹配项。确保用户不会搜索您的字符串分隔符。

您甚至可以使用以下内容将 id 添加到字符串中:

  • 字符串 "11 flipping burgers""12 pumping gas""13 delivering mail"

  • 正则表达式: "(\d+) ([^"]*ping[^"]*)"

  • 示例:http: //jsfiddle.net/RnabN/4/ (30000 个字符串,将结果限制为 100 个)

原文由 sod 发布,翻译遵循 CC BY-SA 2.5 许可协议

如果不进行一些更改,就无法加快 初始 数组查找的速度。您可以通过缓存结果并将它们动态映射到模式来加速后续查找。

1.) 调整你的数据格式。这使得初始查找速度更快。基本上,你预缓存。

 var data = {
    a : ['Ant farm', 'Ant massage parlor'],
    b : ['Bat farm', 'Bat massage parlor']
    // etc
}

2.) 设置缓存机制。

 var searchFor = function(str, list, caseSensitive, reduce){
    str = str.replace(/(?:^\s*|\s*$)/g, ''); // trim whitespace
    var found = [];
    var reg = new RegExp('^\\s?'+str, 'g' + caseSensitive ? '':'i');
    var i = list.length;
    while(i--){
        if(reg.test(list[i])) found.push(list[i]);
        reduce && list.splice(i, 1);
    }
}

var lookUp = function(str, caseSensitive){
    str = str.replace(/(?:^\s*|\s*$)/g, ''); // trim whitespace
    if(data[str]) return cache[str];
    var firstChar = caseSensitive ? str[0] : str[0].toLowerCase();
    var list = data[firstChar];
    if(!list) return (data[str] = []);
    // we cache on data since it's already a caching object.
    return (data[str] = searchFor(str, list, caseSensitive));
}

3.) 使用以下脚本创建预缓存对象。我建议您运行一次并使用 JSON.stringify 创建一个静态缓存对象。 (或在后端执行此操作)

 // we need lookUp function from above, this might take a while
var preCache = function(arr){
    var chars = "abcdefghijklmnopqrstuvwxyz".split('');
    var cache = {};
    var i = chars.length;
    while(i--){
        // reduce is true, so we're destroying the original list here.
        cache[chars[i]] = searchFor(chars[i], arr, false, true);
    }
    return cache;
}

代码可能比您预期的要多一些,但优化和性能并不是免费的。

原文由 BGerrissen 发布,翻译遵循 CC BY-SA 2.5 许可协议

撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
推荐问题