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

Question

我有一个很长的字符串(大小为60MB),我需要在其中找到有多对"<"和">".

---

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

        char pre = '!';
        int match1 = 0;
        for (int j = 0; j < html.Length; j++)
        {
            char c = html[j];
            if (pre == '<' && c == '>') //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) // find a match
            {
                index = html.IndexOf('>', index + 1);
                if (index != -1)
                   match2++;
            }
        } while (index != -1);

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

---

我想知道string.IndexOf运行这么快的神奇是什么？

任何人都可以激励我吗？

---

编辑

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

---

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

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

---

运用 IndexOf

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

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

---

编辑2

在阅读了@Jeffrey Sax评论后,我意识到我在VS中使用Debug模式运行.

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

结果如下:

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

对于正常的一个字符数:141ms VS 111ms.

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

---

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

Answer 1

您是否在Visual Studio中运行计时？如果是这样,那么仅仅因为这个原因你的代码运行速度会慢得多

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

该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正确处理所有额外的复杂性,但它需要付出代价.

Answer 2

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

callvirt    System.String.IndexOf

如果我们使用反射器的力量（尽可能多地），最终会进入

CompareInfo.IndexOf(..)

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