字符串加入和复杂性？

Question

当我需要连接两个字符串时,我使用String.Format(或StringBuilder,如果它发生在代码中的几个地方).

我看到一些优秀的程序员不会注意字符串加入复杂性而只是使用'+'运算符.

我知道使用'+'运算符会使应用程序使用更多内存,但复杂性又如何呢？

Answer 1

这是关于不同的字符串加入我们自己的方法的优秀文章杰夫·阿特伍德的编码恐怖:

替代文字http://www.codinghorror.com/blog/images/coding-horror-official-logo-small.png

微优化剧场的悲剧悲剧

这是帖子的要点.

[显示了几个字符串连接方法 ]

把你发痒的小触发手指从编译键上移开,并考虑一下这一点.哪种方法会更快？

有答案吗？大!

并且..鼓声请...正确答案:

它.只是.不.物!

Answer 2

这个答案假设您在谈论运行时复杂性。

Using+创建一个新的字符串对象，这意味着必须将旧字符串对象的内容复制到新对象中。对于大量串联，例如在紧密循环中，这可能会变成 O(n^2) 操作。

作为非正式证明，假设您有以下代码：

string foo = "a";
for(int i = 0; i < 1000; i++)
{
    foo += "a";
}

循环的第一次迭代，首先将foo("a")的内容复制到一个新的字符串对象中，然后是字面量 "a" 的内容。那是两份。第二次迭代有三个副本；两个来自 new foo，一个来自文字“a”。第 1000 次迭代将有 1001 次复制操作。总份数为2 + 3 + ... + 1001。通常，如果在循环中每次迭代只连接一个字符（并且从一个字符开始），如果迭代次数为 n，则会有2 + 3 + ... + n + 1副本。这与 相同1 + 2 + 3 + ... + n = n(n+1)/2 = (n^2 + n)/2，即 O(n^2)。