如果我有一个超过10,000个元素的大型 JavaScript 字符串数组，如何快速搜索它？
目前我有一个 JavaScript 字符串数组，用于存储工作描述，并允许用户在输入框中动态筛选返回的列表。
假设现在有一个字符串数组，像这样:
var descArr = {"flipping burgers", "pumping gas", "delivering mail"};
如果用户想要搜索："p"
我怎么能够快速搜索一个包含10000+描述的字符串数组呢？显然，由于它们是描述性的，所以我不能对描述数组进行排序，因此二分查找也不可行。而且，由于用户可以通过 "p" 或者 "pi" 或任何字母组合进行搜索，这种部分搜索意味着我无法使用关联数组（即searchDescArray["pumping gas"] ）来加速搜索。
大家有什么想法吗？
由于现实浏览器中的正则表达式引擎在速度方面表现得有些疯狂，那么采用这种方式怎样呢？不再使用数组，而是传递一个巨大的字符串并用标识符分隔单词。
"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个）
如果不进行一些改变，是无法加快初始数组查找速度的。但你可以通过缓存结果并动态映射它们到模式来加快连续查找的速度。
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;
}
可能比您预期的代码多一些，但优化和性能并不是免费的。
这可能不是你想要的答案，因为我对你的设置做了一些假设，但如果你有服务器端代码和数据库，最好通过AJAX调用返回缩小的结果列表，并使用数据库进行过滤（因为它们非常擅长这种事情）。
除了数据库的好处外，如果你只返回所需的变量，而不是输出这么多数据（10000个变量）到基于Web的前端，你还将受益于节省大量带宽。
我无法复现这个问题，我创建了一个天真的实现，在大多数浏览器中，搜索10000个15个字符字符串只需要几毫秒。我无法在IE6中进行测试，但我不相信它比最快的浏览器慢100倍以上，这仍然是几乎瞬间完成的。
你可以自己尝试一下：http://ebusiness.hopto.org/test/stacktest8.htm（请注意，创建时间与问题无关，只是为了获取一些可用数据。）
你可能做错的一件事是尝试渲染所有结果，当用户只输入一个字母或常见字母组合时，这将是一项相当巨大的工作。
我建议尝试使用现成的JS函数，例如jQuery中的autocomplete。它速度快，并且有许多配置选项。
请查看jQuery自动完成演示。
对于大型数据集（1M+），使用Set比Array.includes()快约3500倍。
如果想要速度，必须使用Set。
我刚刚编写了一个需要在1.3M数组中查找字符串的节点脚本。
使用Array的.includes进行10K次查找： 39.27秒
使用Set的.has进行10K次查找： 0.01084秒
使用Set。