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

optimize search through large js string array?

提问by TriFu

if I have a large javascript string array that has over 10,000 elements, how do I quickly search through it?

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

Right now I have a javascript string array that stores the description of a job, and I"m allowing the user to dynamic filter the returned list as they type into an input box.

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

So say I have an string array like so:
var descArr = {"flipping burgers", "pumping gas", "delivering mail"};

所以说我有一个像这样的字符串数组：
var descArr = {"flipping burgers", "pumping gas", "delivering mail"};

and the user wants to search for: "p"

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

How would I be able to search a string array that has 10000+ descriptions in it quickly? Obviously I can't sort the description array since they're descriptions, so binary search is out. And since the user can search by "p"or "pi"or any combination of letters, this partial search means that I can't use associative arrays (i.e. searchDescArray["pumping gas"]) to speed up the search.

如何快速搜索包含 10000 多个描述的字符串数组？显然我无法对描述数组进行排序，因为它们是描述，所以二分搜索已经过时了。而且，由于用户可以通过搜索"p"或"pi"或字母的任意组合，这部分搜索装置，我无法使用关联数组（即searchDescArray["pumping gas"]），以加速搜索。

Any ideas anyone?

任何人的想法？

回答by sod

As regular expression engines in actual browsers are going nuts in terms of speed, how about doing it that way? Instead of an array pass a gigantic string and separate the words with an identifer. Example:

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

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

• 细绳 "flipping burgers""pumping gas""delivering mail"
• 正则表达式： "([^"]*ping[^"]*)"

With the switch /gfor global you get all the matches. Make sure the user does not search for your string separator.

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

You can even add an id into the string with something like:

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

• String "11 flipping burgers""12 pumping gas""13 delivering mail"

• Regex: "(\d+) ([^"]*ping[^"]*)"

• Example: http://jsfiddle.net/RnabN/4/(30000 strings, limit results to 100)

• 细绳 "11 flipping burgers""12 pumping gas""13 delivering mail"

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

• 示例：http: //jsfiddle.net/RnabN/4/（30000 个字符串，限制结果为 100）

回答by BGerrissen

There's no way to speed up an initialarray lookup without making some changes. You can speed up consequtive lookups by caching results and mapping them to patterns dynamically.

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

1.) Adjust your data format. This makes initial lookups somewhat speedier. Basically, you precache.

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

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

2.) Setup cache mechanics.

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.) Use the following script to create a precache object. I suggest you run this once and use JSON.stringify to create a static cache object. (or do this on the backend)

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;
}

Probably a bit more code then you expected, but optimalisation and performance doesn't come for free.

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

回答by aaaaaaaaaaaa

I can't reproduce the problem, I created a naive implementation, and most browsers do the search across 10000 15 char strings in a single digit number of milliseconds. I can't test in IE6, but I wouldn't believe it to more than 100 times slower than the fastest browsers, which would still be virtually instant.

我无法重现该问题，我创建了一个幼稚的实现，并且大多数浏览器都会在一位数的毫秒内搜索 10000 个 15 个字符的字符串。我无法在 IE6 中进行测试，但我不相信它比最快的浏览器慢 100 倍以上，这仍然几乎是即时的。

Try it yourself: http://ebusiness.hopto.org/test/stacktest8.htm(Note that the creation time is not relevant to the issue, that is just there to get some data to work on.)

自己尝试一下：http: //ebusiness.hopto.org/test/stacktest8.htm（请注意，创建时间与问题无关，只是为了获取一些数据。）

One thing you could do wrong is trying to render all results, that would be quite a huge job when the user has only entered a single letter, or a common letter combination.

你可能做错的一件事是试图呈现所有结果，当用户只输入一个字母或一个常见的字母组合时，这将是一项非常艰巨的工作。

回答by Paddy

This may not be an answer for you, as I'm making some assumptions about your setup, but if you have server side code and a database, you'd be far better off making an AJAX call back to get the cut down list of results, and using a database to do the filtering (as they're very good at this sort of thing).

这可能不是你的答案，因为我正在对你的设置做出一些假设，但是如果你有服务器端代码和数据库，你最好通过 AJAX 回调来获取减少的列表结果，并使用数据库进行过滤（因为他们非常擅长这种事情）。

As well as the database benefit, you'd also benefit from not outputting this much data (10000 variables) to a web based front end - if you only return those you require, then you'll save a fair bit of bandwidth.

除了数据库优势之外，您还可以从不向基于 Web 的前端输出这么多数据（10000 个变量）中受益——如果您只返回您需要的数据，那么您将节省相当多的带宽。

回答by medopal

I suggest trying a ready made JS function, for example the autocompletefrom jQuery. It's fast and it has many options to configure.

我建议尝试一个现成的 JS 函数，例如autocomplete来自 jQuery 的函数。它很快，并且有很多配置选项。

Check out the jQuery autocomplete demo

查看jQuery 自动完成演示