c# - 进行字符串连接时的性能 - 算法字符串字符串 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因为它针对构建字符串进行了优化，方法是将它们附加在一起。