C＃的string.IndexOf如何执行得如此之快，比普通的循环查找速度快10倍？

我有一个非常长的字符串（大小为60MB ），我需要在其中找到有多对“”。

---

我首先尝试了自己的方式：

char pre = '!'; int match1 = 0; for (int j = 0; j < html.Length; j++) { char c = html[j]; if (pre == '') //find a match { pre = '!'; match1++; } else if (pre == '!' && c == '<') pre = '<'; } 

上面的代码在我的字符串上运行大约1000毫秒 。

---

然后我尝试使用string.IndexOf

  int match2 = 0; int index = -1; do { index = html.IndexOf('', index + 1); if (index != -1) match2++; } } while (index != -1); 

上面的代码只运行大约150毫秒 。

---

我想知道是什么让string.IndexOf运行如此之快 ？

任何人都可以激励我吗？

---

编辑

好的，根据@ BrokenGlass的回答。 我修改了代码的方式是他们没有检查配对，而是检查字符串中有多少'<'。

---

  for (int j = 0; j ') { match1++; } } 

上面的代码运行大约760毫秒 。

---

使用IndexOf

  int index = -1; do { index = html.IndexOf('<', index + 1); if (index != -1) { match2++; } } while (index != -1); 

上面的代码运行大约132毫秒 。 还是非常快。

---

编辑2

在阅读@Jeffrey Sax评论后，我意识到我在VS中运行调试模式。

然后我在发布模式下构建并运行，好吧， IndexOf仍然更快，但不再那么快。

结果如下：

对于配对计数： 207ms VS 144ms

对于正常的一个字符数： 141ms VS 111ms 。

我自己的代码的表现真的得到了改善。

---

获得的经验：当您执行基准测试时，请在发布模式下执行此操作！

Answer 1

您是否在Visual Studio中运行计时？ 如果是这样的话，单独出于这个原

除此之外，你在某种程度上比较了苹果和橘子。 这两种算法以不同的方式工作。

IndexOf版本在仅查找IndexOf括号和仅 IndexOf括号之间交替显示。 您的代码遍历整个字符串并保留一个状态标志，指示是否正在查找开始或结束括号。 这需要更多的工作，预计会更慢。

这里有一些代码以与IndexOf方法相同的方式进行比较。

 int match3 = 0; for (int j = 0; j < html.Length; j++) { if (html[j] == '<') { for (; j < html.Length; j++) if (html[j] == '>') match3++; } } 

在我的测试中，这实际上比IndexOf方法快3倍。 原因？ 字符串实际上并不像单个字符序列那么简单。 有标记，重音符号等String.IndexOf可以正确处理所有额外的复杂性，但需String.IndexOf 。

Answer 2

我唯一想到的是IndexOf iniside字符串类的实际实现，即该调用

 callvirt System.String.IndexOf 

如果我们使用reflection器的功率（尽可能多）最终进入

 CompareInfo.IndexOf(..) 

调用，而不是使用超快速Windows本机函数FindNLSString ：

Answer 3

直接比较托管实现和String.IndexOf方法有点谬论。 IndexOf的实现主要是本机代码，因此具有与托管实现不同的一组性能特征。 特别是本机代码避免了类型安全检查及其相应的开销，这些开销由CLR在托管算法中注入。

一个例子是使用数组索引

 char c = html[j]; 

在托管代码中，此语句将validationj是数组html的有效索引，然后返回该值。 本机代码等效只返回一个内存偏移量，无需额外的检查。 缺少检查为本机代码提供了固有的优势，因为它可以避免在循环的每次迭代中添加额外的分支指令。

请注意，这个优势并不是绝对的。 JIT可以很好地检查这个循环并确定j永远不会是无效索引并且忽略生成的本机代码中的检查（并且在某些情况下它确实执行此操作IIRC）。

Answer 4

我希望string.IndexOf与您的第一个代码示例相比，运行速度至少快两倍（除了可能在那里进行的任何其他优化），因为您在每次迭代中都检查了开始和结束字符。 另一方面，使用string.IndexOf实现只有在成功找到起始字符后才会检查结束字符。 这大大减少了每次迭代的操作次数（比较少一次）。

Answer 5

使用switch语句而不是if测试也可以加快速度。 这段代码偶尔会打败我机器上的代码索引。

  int count = 0; bool open = false; for (int j = 0; j < testStr.Length; j++) { switch (testStr[j]) { case '<': open = true; break; case '>': if (open) count++; open = false; break; } }