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

Question

如果我有一个包含超过 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 许可协议

Answer 1

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

• 字符串 "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 许可协议

Answer 2

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

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 许可协议