1

在我的 JSP 页面上，我有一个可以包含 60k+ 个对象的选择对象。我将这些 60k+ 对象存储到一个名为“masterList”的 javascript 数组中。我为用户提供了一个输入框来过滤列表。过滤基于“开始于..”的方法。有没有更快的方法来做到这一点？当用户在输入框中输入零个或 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;
        }
    }
4

7 回答 7

2

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

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

例如

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

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

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

于 2012-07-13T19:52:37.260 回答
1

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

该组件使您能够：

  • 如果您仍想推送所有元素服务器端，只需从数组中自动完成；
  • 构建一个更复杂的自动完成模式，它使用 web 服务来提供要显示的元素（考虑服务器端缓存，如下面的评论中建议的那样是个好主意）。
于 2012-07-13T19:53:02.057 回答
1

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

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

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

否则，您应该创建一个对象目录。就像是：

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

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

于 2012-07-13T19:56:46.550 回答
1

[编辑] 参见这个 jsfiddle示例，使用 100.000 个元素的初始数组。

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

第一个优化是对数组进行排序。其次，您可以通过将其值转换为现成的Option对象来准备大数组。第三，你有没有想过应用新的 Arraymap和filter方法？第四，使用 RegExtest代替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];
}

为了浏览器兼容性，您可能希望使用 shims 进行映射和过滤

于 2012-07-13T21:07:01.497 回答
0

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

下一个最佳选择是按照@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”是否是另一个字符串？

于 2012-07-13T20:00:03.493 回答
0

要以最快的方式遍历数组，请最好执行 for 循环，例如...

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

因为这节省了对每个循环的评估（例如

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

如果你必须使用一个数组，至少将它们分成一个数组，a's，b's，c's 等等......

于 2012-07-13T20:10:32.720 回答
0

好的，这是您遇到的最大问题以及为什么其他解决方案（包括我的其他解决方案）都不起作用：

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 步。

于 2012-07-13T22:06:47.413 回答