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

本文关键字：字符串 算法 性能 连接 执行 | 更新日期: 2023-09-27 18:04:24

我使用下面的代码来附加字符串

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。

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

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

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将构建字符串进行了优化。

假设-根据Matt Burland的回答-通过给定算法之一创建长度为n的字符串的时间成本为受复制字符数量的影响，观察到的时间可以通过计算这两种算法在很大程度上解释。这产生了O(n2)和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

这可以得到

c (2 <一口> k + ) = ( k + 1) 2 <一口> k + ( k + 3)一个

, k 和选择这样 n = 2 <一口> k + , & lt;2 <一口> k ;这很容易通过完全归纳法得到验证。这是O ( k 2 <一口> k ),即O (n 日志<子> 2 n ),即O (n 日志 n ),

说明:成本比较

原算法清楚地复制了n(n+1)/2个字符，因此是0 (n2)。

修改后的算法显然复制的字符要少得多;对于给定的10,000个字符串:

c(10000) =
c(213 + 1808) =

(13+1) * 8192 + 16 * 1808 =
143616

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

进一步优化

给定字符串由单个字符填充，和假设 String.Substring不复制字符串，根据比较-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);
}

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

c <子> 2 ( n ) = n + c <子> 2 (⌈ n /2⌉)

，从中我们可以推导出

c <子> 2 ( n ) = 2 _n_ + d ( n )

其中，如果n是2的幂，则d(n)为-1，否则在m的二进制展开中等于0的"内部"(即既不是前导也不是尾位)数;等价地，d(n)由m∈∈的第一个匹配情况定义:

d(2m) = -1
d (2 ) = d ()
d(m) = m

中必要(非前导)0二进制位数的个数

c2的表达式也可以用完全归纳法来验证，它是O(n + log n)，即O(n)。

从这个算法中删除递归是相当简单的。

在OP的情况下，这个算法复制c2(10,000) = 20,000 + d(110000110101000002) = 20,006个字符因此看起来要快7倍。

其他言论
  • 此分析适用于创建任何字符串的倍数，而不仅仅是"5"。
    • 构造OP字符串最有效的方法大概是String('5', ite)。
  • 如果使用StringBuilder构建已知大小的字符串，可以使用StringBuilder(capacity)来减少分配。
  • 此分析适用于。net以外的其他环境。
  • 在C语言中，分配一个合适大小的缓冲区(包括''0' !)，复制要重复的字符串，然后重复添加缓冲区中已填充部分的副本，直到缓冲区满。
相关文章：