模式匹配字符串时，Javascript / jQuery更快替代$ .inArray
我在Javascript（~100,000）中有大量的单词，我希望能够根据文本模式快速返回它们的子集。
例如，我想返回所有以模式开头的单词，因此输入hap应该给我["happy", "happiness", "happening", etc, etc] ，结果。
如果有可能我想在不迭代整个数组的情况下这样做。
这样的事情不够快：
// data contains an array of beginnings of words eg 'hap' $.each(data, function(key, possibleWord) { found = $.inArray(possibleWord, words); // do something if found }
关于如何在不迭代整个单词集的情况下快速将集合减少到可能的匹配的任何想法？ 如果有帮助，单词数组按字母顺序排列。
如果您只是想搜索前缀，那么就有数据结构，例如Trie和Ternary搜索树
一个快速的谷歌搜索和一些承诺Javascrit Trie和自动完成实现显示：
http://ejohn.org/blog/javascript-trie-performance-analysis/
使用trie自动完成
http://odhyan.com/blog/2010/11/trie-implementation-in-javascript/
我完全不知道这是否更快 （ jsperf测试可能是有序的…），但你可以用一个巨大的字符串和一个RegExp搜索代替数组：
var giantStringOfWords = giantArrayOfWords.join(' '); function searchForBeginning(beginning, str) { var pattern = new RegExp('\\b' + str + '\\w*'), matches = str.match(pattern); return matches; } var hapResults = searchForBeginning('hap', giantStringOfWords);
最好的方法是更好地构建数据。 使用像“hap”这样的键创建一个对象。 该成员包含一系列单词（如果您想节省空间，则为单词后缀）或用于正则表达式搜索的单独字符串。
这意味着你将有更短的对象来迭代/搜索。 另一种方法是对数组进行排序并使用二进制搜索模式。 这里有关于技术和优化的良好对话： http ： //ejohn.org/blog/revised-javascript-dictionary-search/
我想使用原始的javascript可以帮助一点，你可以这样做：
var arr = ["happy", "happiness", "nothere", "notHereEither", "happening"], subset = []; for(var i = 0, len = arr.length; i < len; i ++) { if(arr[i].search("hap") !== -1) { subset.push(arr[i]); } } //subset === ["happy", "happiness","happening"]
此外，如果数组是有序的，如果第一个字母大于搜索的第一个字母，则可以提前中断，而不是循环整个数组。
var data = ['foo', 'happy', 'happiness', 'foohap']; jQuery.each(data, function(i, item) { if(item.match(/^hap/)) console.log(item) });
如果你有一个数组中的数据，你将不得不循环整个事情。
一个非常简单的优化是页面加载通过你的大字数组并记下每个起始字母适用的索引范围。 例如，在下面的例子中，“a”字从0到2，“b”字从3变为4，等等。然后，当实际进行模式匹配时，只查看适用的范围。 虽然显然有些字母会比其他字母有更多的单词，但是给定的搜索只需要查看平均100,000 / 26个单词。
// words array assumed to be lowercase and in alphabetical order var words = ["a","an","and","be","blue","cast","etc."]; // figure out the index for the first and last word starting with // each letter of the alphabet, so that later searches can use // just the appropriate range instead of searching the whole array var letterIndexes = {}, i, l, letterIndex = 0, firstLetter; for (i=0, l=words.length; i
另请注意，当搜索单词数组中的（范围）时，一旦找到匹配项，我会设置一个标记，表示我们已经超过了模式之前按字母顺序排列的所有单词，现在正在通过匹配单词。 这样一旦模式不再匹配，我们就可以突破循环。 如果模式根本不匹配，我们仍然会查看第一个字母的所有单词。
此外，如果您在用户输入时这样做，当字母添加到模式的末尾时，您只需搜索前一个子集，而不是整个列表。
PS当然，如果你想通过第一个字母打破单词列表，你可以很容易地做到服务器端。