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

Question

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

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

假设我有一个字符串数组，如下所示：

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

用户想要搜索的是："p"

如何快速搜索包含10000+描述的字符串数组？显然，我不能对描述数组进行排序，因为它们是描述，所以二进制搜索是不存在的。由于用户可以通过"p"、"pi"或任意字母组合进行搜索，因此这种部分搜索意味着我不能使用关联数组(即searchDescArray["pumping gas"] )来加快搜索速度。

有没有人有主意？

Answer 1

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

• String "flipping burgers""pumping gas""delivering mail"
• Regex："([^"]*ping[^"]*)"

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

您甚至可以将id添加到字符串中，如下所示：

• String "11 flipping burgers""12 pumping gas""13 delivering mail"
• Regex："(\d+) ([^"]*ping[^"]*)"
• Example：http://jsfiddle.net/RnabN/4/ (30000个字符串，限制结果不超过100个)

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.)使用以下脚本创建一个precache对象。我建议您运行一次，然后使用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;
}

可能比你预期的要多一点代码，但是优化和性能不是免费的。

Answer 3

这可能不适合您，因为我对您的设置做了一些假设，但是如果您有服务器端代码和数据库，您最好进行一个AJAX回调来获得精简的结果列表，并使用数据库进行过滤(因为他们非常擅长这类事情)。

除了数据库的好处，你也可以从不输出这么多数据(10000个变量)到基于web的前端中受益-如果你只返回你需要的数据，那么你将节省相当多的带宽。