在javascript中搜索字符串的最快方法

Question

我的页面上有一个隐藏字段,用于存储空格分隔的电子邮件列表.我可以在该字段中发送最多500封电子邮件.

如果给定的电子邮件已经存在于该列表中,那么搜索的最快方式是什么？我需要循环搜索多个电子邮件

1. 使用RegEx查找匹配项

2. 使用indexOf()

3. 将列表转换为javascript字典,然后搜索

如果这完全相同,请告诉我其他问题.谢谢

编辑:感谢大家的宝贵意见和答案.基本上我的用户在db中有一个电子邮件列表(0-500).向用户显示他自己的联系人列表.然后,用户可以从他的联系人列表中选择一个或多个电子邮件添加到列表中.我想在客户端确保他没有添加重复的电子邮件.整个操作由ajax驱动,因此需要jsvascript.

Answer 1

答案是:这取决于.

• 这取决于你实际想要测量的内容.
• 这取决于您搜索的数量与您搜索的数量之间的关系.
• 这取决于JavaScript的实现.不同的实现通常具有完全不同的性能特征.这是"不要过早优化"规则特别适用于跨实现JavaScript的众多原因之一.

...但是如果你要寻找的总数比你总要多得多,那么String#indexOf除非你可以创建一次字典并重复使用它(不仅仅是这一个寻找X条目的循环,而是每个循环寻找X条目) ,我倾向于怀疑是你的用例),在这种情况下,建立500键字典并使用它的速度更快.

我在jsperf上组合了一个测试用例,比较了查找包含500个以空格分隔的唯一条目的字符串中的五个字符串的结果.请注意,jsperf页面比较了一些苹果和橙子(我们可以忽略设置和我们忽略的设置类型的情况),但jsperf很难分开它,我决定将其作为读者的练习.

在我对我实际认为你正在做的事情的测试中,Chrome,Firefox,IE6,IE7和IE9的表现String#indexOf最快.Opera做得RegExp alternation最快.(请注意,IE6和IE7没有Array#indexOf;其他人都这样做.)如果你可以忽略字典设置时间,那么使用字典就是不折不扣的赢家.

这是准备代码:

// ==== Main Setup
var toFind = ["aaaaa100@zzzzz", "aaaaa200@zzzzz", "aaaaa300@zzzzz", "aaaaa400@zzzzz", "aaaaa500@zzzzz"];
var theString = (function() {
 var m, n;

 m = [];
 for (n = 1; n <= 500; ++n) {
  m.push("aaaaa" + n + "@zzzzz");
 }
 return m.join(" ");
})();

// ==== String#indexOf (and RegExp) setup for when we can ignore setup
var preppedString = " " + theString + " ";

// ==== RegExp setup for test case ignoring RegExp setup time
var theRegExp = new RegExp(" (?:" + toFind.join("|") + ") ", "g");

// ==== Dictionary setup for test case ignoring Dictionary setup time
var theDictionary = (function() {
 var dict = {};
 var index;
 var values = theString.split(" ");
 for (index = 0; index < values.length; ++index) {
  dict[values[index]] = true;
 }
 return dict;
})();

// ==== Array setup time for test cases where we ignore array setup time
var theArray = theString.split(" ");

该String#indexOf测试:

var index;
for (index = 0; index < toFind.length; ++index) {
 if (theString.indexOf(toFind[index]) < 0) {
  throw "Error";
 }
}

的String#indexOf(忽略设置)测试,在此我们忽略了把空间的大串的两端的(小)的开销:

var index;
for (index = 0; index < toFind.length; ++index) {
 if (preppedString.indexOf(toFind[index]) < 0) {
  throw "Error";
 }
}

在RegExp交替的测试:

// Note: In real life, you'd have to escape the values from toFind
// to make sure they didn't have special regexp chars in them
var regexp = new RegExp(" (?:" + toFind.join("|") + ") ", "g");
var match, counter = 0;
var str = " " + theString + " ";
for (match = regexp.exec(str); match; match = regexp.exec(str)) {
 ++counter;
}
if (counter != 5) {
 throw "Error";
}

在RegExp交替(忽略设置)测试中,我们忽略它需要建立RegExp对象,并把空间的大串的两端(我不认为这也适用于您的情况的时候,你要寻找的地址会是静态的):

var match, counter = 0;
for (match = theRegExp.exec(preppedString); match; match = theRegExp.exec(preppedString)) {
 ++counter;
}
if (counter != 5) {
 throw "Error";
}

该词典的测试:

var dict = {};
var index;
var values = theString.split(" ");
for (index = 0; index < values.length; ++index) {
 dict[values[index]] = true;
}
for (index = 0; index < toFind.length; ++index) {
 if (!(toFind[index] in dict)) {
  throw "Error";
 }
}

该词典(忽略设置)测试中,我们并不担心建立时间字典; 注意,这是不同的比RegExp交替(忽略设置),因为它假定测试整体名单是不变的:

var index;
for (index = 0; index < toFind.length; ++index) {
 if (!(toFind[index] in theDictionary)) {
  throw "Error";
 }
}

该Array#indexOf测试(注意,有些很老的JavaScript的实现可能没有Array#indexOf):

var values = theString.split(" ");
var index;
for (index = 0; index < toFind.length; ++index) {
 if (values.indexOf(toFind[index]) < 0) {
  throw "Error";
 }
}

的Array#indexOf(忽略设置)测试,其中相同的字典(忽略设置)假定总体列表是不变的:

var index;
for (index = 0; index < toFind.length; ++index) {
 if (theArray.indexOf(toFind[index]) < 0) {
  throw "Error";
 }
}

Answer 2

您首先需要确保您\xe2\x80\x99 实际上拥有正确的解决方案，而不是寻找最快的解决方案。因为有四种情况会出现电子邮件地址，而简单的搜索可能会失败：

\n\n

\n
1. 独自的：user@example.com
\n
2. 一开始：user@example.com ...
\n
3. 在最后：... user@example.com
\n
4. 之间：... user@example.com ...
\n

\n\n

现在让\xe2\x80\x99s 分析每个变体：

\n\n

\n

1. 要允许任意输入，您需要正确转义输入。您可以使用以下方法来执行此操作：

   \n\n

   RegExp.quote = function(str) {\n    return str.toString().replace(/(?=[.?*+^$[\\]\\\\(){}-])/g, "\\\\");\n};\n

   \n\n

   要匹配所有四种情况，您可以使用以下模式：

   \n\n

   /(?:^|\\ )user@example\\.com(?![^\\ ])/\n

   \n\n

   因此：

   \n\n

   var inList = new RegExp("(?:^| )" + RegExp.quote(needle) + "(?![^ ])").test(haystack);\n

\n

2. 使用indexOf有点复杂，因为您需要手动检查边界：

   \n\n

   var pos = haystack.indexOf(needle);\nif (pos != -1 && (pos != 0 && haystack.charAt(pos-1) !== " " || haystack.length < (pos+needle.length) && haystack.charAt(pos+needle.length) !== " ")) {\n    pos = -1;\n}\nvar inList = pos != -1;\n

\n

3. 这个相当简单：

   \n\n

   var dict = {};\nhaystack.match(/[^\\ ]+/g).map(function(match) { dict[match] = true; });\nvar inList = dict.hasOwnProperty(haystack);\n

\n

\n\n

现在要测试哪种变体最快，您可以在jsPerf进行测试。

\n