15

我有一个很长的字符串（大小为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 ms。

然后我尝试使用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 ms。

我想知道让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 中以调试模式运行。

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

结果如下：

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

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

我自己的代码的性能确实得到了改善。

经验教训：当您进行基准测试时，请在发布模式下进行！

4

5 回答 5

9

您是否在 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正确处理所有额外的复杂性，但这是有代价的。

于 2012-05-09T16:06:52.343 回答
5

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

callvirt    System.String.IndexOf

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

CompareInfo.IndexOf(..)

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

在此处输入图像描述

于 2012-05-09T16:15:18.920 回答
4

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

一个例子是使用数组索引

char c = html[j];

在托管代码中，此语句将验证这j是数组的有效索引html，然后返回该值。本机代码等效项仅返回内存偏移量，无需额外检查。这种检查的缺乏使本机代码在这里具有固有的优势，因为它可以避免在循环的每次迭代中添加额外的分支指令。

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

于 2012-05-09T16:25:42.083 回答
1

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

于 2012-05-09T15:46:14.903 回答
1

使用 switch 语句而不是 if 测试也会加快速度。这段代码偶尔会胜过我机器上的 indexof 代码。

        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;         
            }
        }
于 2012-05-09T16:32:29.063 回答