进行字符串连接时的性能 - 算法字符串字符串 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 将它们组合在一起针对 构建字符串 进行了优化。

Answer 2

假设 - 根据 Matt Burland 的回答 - 通过给定算法之一创建长度为 n 的字符串的时间成本是以复制的字符数为主，观察到的时间可以在很大程度上通过对两种算法的计算来解释。这产生 O(n²) 和 O(n log n)，并且对于长度 10,000，比率为 348:1。该算法可能会在 Java 中改进为 O(n)，但在 .NET 中显然不是。

改进算法的成本

查看改进后的算法，复制的字符数c(n)服从以下递推关系：

c(0) = 0
c(1) = 1
c(n) = c(⌊n/2⌋) + c(⌈n/2⌉) + n

这个可以解决yield

c(2^k + a) = (k + 1)2^k + (k + 3)a

其中选择 k 和 a 以便 n = 2^k + a , a < 2^k;这很容易通过完全归纳法得到证实。这是 O(k 2^k), 即 O(nlog₂n),即O(nlogn),

说明：成本比较

原算法显然复制了n(n+1)/2个字符，因此是O( n²).

修改后的算法显然复制了更少的字符；对于给定的 10,000 个字符串：

c(10000) =
c(2¹³ + 1808) =
(13+1) * 8192 + 16 * 1808 =
143,616

而原始算法复制了 50,005,000 个字符，比例约为 1 : 348，与观察到的比率 1:250 在一个数量级内一致。不完全匹配确实表明内存管理等其他因素可能很重要。

进一步优化

鉴于字符串由单个字符填充，假设 String.Substring 不复制字符串，根据 comparison-of-substring-operation-performance-between-net-and-java，这在 Java 中是正确的，但在 中不是 .NET，我们可以改进第二种算法（不使用 StringBuilder 或 String('5', ite)）通过不断加倍构造的字符串，在必要时添加一个额外的字符：

private static string getStr(int p)
{
    if(p == 0)
        return "";
    if(p == 1)
        return "5";
    string s = getStr ((p+1) / 2);
    if( s.Length + s.Length == p )
        return s + s;
    else
        return s + s.Substring(0, p - s.Length);
}

对于这个算法复制的字符数c₂(n)我们有

c₂(n) = n + c₂(⌈n/2⌉)

我们可以从中得出

c₂(n) = 2_n_ + d(n)

如果 n 是 2 的幂，则 d(n) 为 -1，否则为“内部”(即在 m 的二进制扩展中前导和尾随) 数字均不等于 0；等效地，d(n) 由 m ∈ ℕ in:

的第一个匹配案例定义

d(2^m) = -1
d(2 m) = d(m)
d(m) = the number of essential (non-leading) 0 binary digits in m

c₂的表达式也可以通过完全归纳法验证为O(n + log n), 即 O(n).

从该算法中删除递归相当简单。

在 OP 的例子中，这个算法复制 c₂(10,000) = 20,000 + d(11000011010100000₂) = 20,006 个字符因此看起来要快 7 倍。

其他备注

此分析适用于创建任何字符串的倍数，而不仅仅是 "5"。
构造 OP 字符串的最有效方法大概是 String('5', ite)。
如果使用 StringBuilder 构建已知大小的字符串，可以使用 StringBuilder(capacity) 来减少分配。
此分析适用于 .NET 以外的其他环境。
在C中，分配一个合适大小的缓冲区（包括'[=18=]'!），将要重复的字符串复制进去，然后重复追加缓冲区已填充部分的副本，直到满为止。

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

performance while doing string concatenation - algorithm string strings c#

c#

string

algorithm

string-concatenation

改进算法的成本

说明：成本比较

进一步优化

其他备注