ReverseString,一个C#面试问题

Question

我有一个面试问题,问我对初级程序员写的一段代码的"反馈".他们暗示可能存在问题,并表示将大量使用大字符串.

public string ReverseString(string sz)
{
    string result = string.Empty;
    for(int i = sz.Length-1; i>=0; i--)
    {
      result += sz[i]
    }
    return result;
}

我无法发现它.我没有看到任何问题.事后我可以说用户应该调整大小,但看起来C#没有调整大小(我是一个C++人).

我最后编写的东西就像使用迭代器一样,如果可能的话,容器中的[x]不能随机访问,所以它可能很慢.和misc事情.但我绝对说我从来没有优化C#代码,所以我的想法可能没有让我在面试中失败.

我想知道,这段代码有什么问题,你们看到了吗？

-编辑-

我将其更改为维基,因为可以有几个正确的答案.此外,我很高兴我明确表示我从来没有优化过C#程序并且提到了misc其他的东西.哎呀.我一直认为C#对这些类型的东西没有任何性能问题.哎呀.

Answer 1

最重要的是？这将明显地吮吸性能 - 它必须创建大量字符串(每个字符一个).最简单的方法是:

public static string Reverse(string sz) // ideal for an extension method
{
    if (string.IsNullOrEmpty(sz) || sz.Length == 1) return sz;
    char[] chars = sz.ToCharArray();
    Array.Reverse(chars);
    return new string(chars);
}

Answer 2

问题是字符串连接是昂贵的,因为字符串在C#中是不可变的.给出的示例将在每次迭代时创建一个字符长一个字符串的新字符串,效率非常低.为避免这种情况,您应该使用StringBuilder类,如下所示:

public string ReverseString(string sz)
{
    var builder = new StringBuilder(sz.Length);
    for(int i = sz.Length-1; i>=0; i--)
    {
      builder.Append(sz[i]);
    }
    return builder.ToString();
}

StringBuilder是专门为这样的场景编写的,因为它使您能够连接字符串而没有过多内存分配的缺点.

你会注意到我为StringBuilder提供了一个你不经常看到的初始容量.如您所知,开始的结果长度,这将删除不必要的内存分配.

通常发生的是它为StringBuilder分配一定量的内存(默认为16个字符).一旦内容试图超过该容量,它就会使自己的能力增加一倍(并且继续).这比每次分配内存要好得多,正如普通字符串所发生的那样,但如果你能避免这种情况,那就更好了.

Answer 3

对目前给出的答案的一些评论:

• 他们中的每一个(到目前为止!)都会在代理对和组合字符上失败.哦,Unicode的乐趣.反转字符串与反转字符序列不同.
• 我喜欢Marc对null,空和单字符输入的优化.特别是,这不仅可以快速得到正确答案,而且还可以处理null(其他答案都没有)
• 我原本以为ToCharArray随后Array.Reverse会是最快的,但它确实会创建一个"垃圾"副本.
• 该StringBuilder解决方案创建一个字符串(而不是char数组)并在您调用之前对其进行操作ToString.没有涉及额外的复制......但是还有更多工作要么保持长度等等.

哪个是更有效的解决方案？好吧,我必须对它进行基准测试才能有任何想法 - 但即便这样也不会说出整个故事.你是否在内存压力很大的情况下使用它,额外的垃圾真的很痛苦？您的内存与CPU等有多快？

与往常一样,可读性通常是王者 - 而且在这方面它并没有比Marc的答案好得多.特别是,没有任何一个错误的余地,而我实际上必须考虑验证其他答案.我不喜欢思考.它伤害了我的大脑,所以我尽量不去做.使用内置Array.Reverse声音对我来说要好得多.(好吧,所以它仍然在代理等方面失败,但是嘿......)

Answer 4

由于字符串是不可变的,因此每个+=语句将通过在最后一步中复制字符串以及单个字符来创建新字符串以形成新字符串.实际上,这将是O(n ²)算法而不是O(n).

更快的方法是(O(n)):

// pseudocode:
static string ReverseString(string input) {
    char[] buf = new char[input.Length];
    for(int i = 0; i < buf.Length; ++i)
       buf[i] = input[input.Length - i - 1];
    return new string(buf);
}