快速循环通过Javascript数组

Fast loop through Javascript array

本文关键字：Javascript 数组 循环      更新时间：2023-09-26

在我的JSP页面上，我有一个select对象，它可以包含60k多个对象。我将这些60k多个对象存储到一个名为"masterList"的javascript数组中。我为用户提供了一个用于筛选列表的输入框。筛选基于"从..开始"的方法。有更快的方法吗？当用户在输入框中输入0或1个字符时，我注意到性能问题。

这就是我的代码现在的样子。

    var numShown = 0;
    var listLength = masterList.length;     
    for(i = 0; i < listLength; i++){
        if(masterList[i].search(re) != -1){
            selectBox[numShown] = new Option(masterList[i], masterList[i]);
            numShown++;
        }
        // Stop when the number to show is reached and input present
        if(input.value != "" && numShown == maxToShow){
            break;
        }
    }

每次通过循环创建的Option（）对象是什么？这本身可能是性能问题的根源。你不太可能一直都需要创建新的对象，所以如果你能添加代码，这将有助于优化你的代码。

开始优化搜索时间的一个非常基本的方法是创建第二个对象，该对象包含master列表中每个字母的起始索引。请注意，如果您的master列表数据在用户使用时发生更改，则需要重新计算索引对象。

例如

var masterList = [aardvark, apple, balloon, blue, cat, dog];
var indexes = {'a':0, 'b':2, 'c':4, 'd':5};

每次用户键入时，取他们键入的第一个字符，并在"indexes"对象中引用其起始索引。然后从该索引开始for循环。还要记住，当您没有找到匹配项，或者将搜索扩展到字母匹配范围之外时，必须停止for循环。基本上，当你的初始搜索条件不满足时，一直搜索到master列表的末尾是没有意义的。

其他注意事项：您需要在for循环中使用var声明i。不管你是否知道，通过使用listLength缓存长度已经做了一件好事。否则，Javascript将在每次迭代中重新计算masterList.length。

[edit]请参阅此jsfiddle示例，使用100.000个元素的初始数组。

除了其他或多或少有用的建议：

第一个优化是对数组进行排序。其次，可以通过将大数组的值转换为现成的Option对象来准备大数组。第三，您是否想过应用新的Array map和filter方法？第四，使用RegEx test代替search。有了这些，你可以将你的过滤代码减少为：

//once, on page load
masterlist = masterlist
             .sort()
             .map(function(item){return new Option(item,item);});
//filtering
var optsfiltered = masterlist.filter(function(item){
     re.lastIndex = 0;
     return re.test(item.value);
    }).slice(0,maxToShow);
//replace selectBox options
selectBox.options.length = 0;
for (var i=0;i<optsfiltered.length;i++){
  selectBox[i] = optsfiltered[i];
}

为了与浏览器兼容，您可能需要使用垫片来映射和过滤

JQuery UI为您提供了一个很好的自动完成组件，如果您将60k元素推送到客户端，则可能会认为您存在设计缺陷。

此组件使您能够：

  • 如果您仍然想在服务器端推送所有元素，只需从数组中自动完成即可
  • 构建一个更复杂的自动完成模式，该模式使用Web服务来提供要显示的元素（考虑下面注释中建议的服务器端缓存是个好主意）

您的主要问题是每次都要扫描整个列表。这是你可以避免的，

一种方法是对列表进行排序。通过这样做，您可以确定在比赛结束后搜索何时可以停止扫描。

您还应该执行二进制搜索，而不是扫描。这可以在排序列表中相对容易地完成。

否则，您应该创建一个对象目录。类似于：

{
   aa: ['aardvark', 'aardwolf' ],
   ab: ['abstain'.....
   ...
}

这减少了真正必要的扫描量

性能的最佳选择是在输入后加载数据。也就是说，当用户键入"tes"时，服务器会发回一个类似["test", ...]的JSON字符串。

下一个最好的选择是像@Dancrumb建议的那样，把东西掰成树。

如果你不能做到这两个，那么下一个最好的方法是确保你的数组有序，并对起点进行二进制搜索。Nicholas C.Zakas在这里有一个很好的例子：http://www.nczonline.net/blog/2009/09/01/computer-science-in-javascript-binary-search/

这会让你从O(N)到O(lg(N))

您必须稍微修改它，以搜索以您的值开头而不是等于您的值的字符串，然后向后搜索第一个实例。

更新

刚刚看到你在使用.search。这意味着你不能使用这些方法中的任何一种，并且只能在服务器上进行昂贵的搜索或在客户端上进行高昂的搜索。考虑检查它是否以值开头，以进行更快的搜索：如何检查字符串"；StartsWith"；另一根绳子？

要以最快的方式循环数组，最好是像。。。

for(var z =listLength;--z;) { do what ever }

因为这会在每个循环上保存一个评估（例如

如果我是你，我会使用不同的格式来保存它进行快速搜索，比如Trie

如果你必须使用一个数组，至少要将它们拆分成一个由a、b、c等组成的数组…

if(masterList[i].search(re) != -1)

在填充列表之前，您将对每个条目执行正则表达式搜索这不仅是一项成本高昂的操作，还意味着你可能对单词中间的匹配感兴趣，这意味着你不能依赖于每个人提出的基于前缀的优化。

如果（A）你有很高的命中率，（B）你真的，真的想做search:，这里有一种方法会很好地工作

  1. 当用户键入一个字母，例如"a"时，开始搜索。查找所有符合您限制的项目，例如5。将条目保存到缓存中。例如：

    myCache['a'] = {
    entries: ['aaaa', 'aaab', 'aaac', 'aaad', 'aaae'],
    lastIndex: 5
};

  2. 当用户键入下一个字符时，现在字符串是"ab"，取字符串减去一个字符，得到"a"，查看myCache["a"]并检查值，得到与"aaab"匹配的值，但其他所有操作都失败。你还需要4个。

  3. 从myCache["a"].lastIndex + 1开始。继续搜索，直到找到匹配项。将你的结果存储在缓存中，你就得到了：

    myCache['ab'] = {
    entries: ['aaab', 'aaba', 'aabb', 'aabc', 'aabd'],
    lastIndex: 29
};

  4. 随着字符串长度的增加，重复步骤2和3。

相关文章：