字符串连接时的性能 - 算法字符串字符串c#

Question

我使用以下代码追加字符串

string res = string.Empty;
int ite = 100000;
for(int i= 0; i < ite; i++)
{
    res += "5";
}

这花费了很多时间,所以我后来将代码更改为

string res = string.Empty;
int ite = 100000;
res = getStr(ite / 2) + getStr(ite - (ite / 2)); 

//body of getStr method
private static string getStr(int p)
{
    if (p == 1)
        return "5";
    else if (p == 0)
        return string.Empty;
    string r1 = getStr(p / 2); //recursive
    string r2 = getStr(p - (p / 2)); //recursive  
    return (r1 + r2);
}

在我看来,实际上没有做任何事情,因为字符串连接的次数与之前的方法大致相同.

但是使用这种方法可以显着提高性能,因为代码大约需要2500毫秒(在我的机器上),现在需要10毫秒.

我在cpu时间运行了一个分析器,无法理解为什么性能有所改善.任何人都可以解释一下.

注意:我故意不使用StringBuilder,以便了解上述内容.

Answer 1

你需要考虑为什么字符串连接很慢.字符串是不可变的,所以当你这样做时:

someString+= "5";

您必须将复制所有内容的someString和另一个字符串,它是一个大的,然后复制的5一部分.如果你考虑一下,字符串越长越慢.

使用递归函数,您可以采用分而治之的策略来帮助最大限度地减少所需的大字符串连接数.例如,如果您的长度为8,那么在第一种情况下您将执行以下操作:

"5" + "5" 
"55" + "5"
"555" + "5"
"5555" + "5"
"55555" + "5"
"555555" + "5"
"5555555" + "5"    // 7 total concatenations

在你的递归模型中:

"5" + "5"         // Four times
"55" + "55"       // twice
"5555" + "5555"   // once 

所以你做的连接不那么大.

而且,当然,我认为OP从他们的评论中知道这一点,但对其他人而言; 如果你需要连接字符串中的任何不平凡的数字,使用StringBuilder的,因为它是优化建设字符串由Append荷兰国际集团在一起.