ReverseString，一个 C# 面试问题

ReverseString, a C# interview-question

提问by

I had an interview question that asked me for my 'feedback' on a piece of code a junior programmer wrote. They hinted there may be a problem and said it will be used heavily on large strings.

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

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

I couldn't spot it. I saw no problems whatsoever. In hindsight I could have said the user should resize but it looks like C# doesn't have a resize (i am a C++ guy).

我没发现。我没有看到任何问题。事后看来，我可以说用户应该调整大小，但看起来 C# 没有调整大小（我是一个 C++ 人）。

I ended up writing things like use an iterator if its possible, [x] in containers could not be random access so it may be slow. and misc things. But I definitely said I never had to optimize C# code so my thinking may have not failed me on the interview.

如果可能的话，我最终编写了诸如使用迭代器之类的东西，容器中的 [x] 不能随机访问，因此它可能会很慢。和杂项。但我肯定地说我从来没有优化过 C# 代码，所以我的想法可能没有让我在面试中失败。

I wanted to know, what is the problem with this code, do you guys see it?

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

-edit-

-编辑-

I changed this into a wiki because there can be several right answers. Also i am so glad i explicitly said i never had to optimize a C# program and mentioned the misc other things. Oops. I always thought C# didnt have any performance problems with these type of things. oops.

我把它改成维基，因为可以有几个正确的答案。我也很高兴我明确地说我从来没有优化 C# 程序并提到了其他东西。哎呀。我一直认为 C# 对这些类型的东西没有任何性能问题。哎呀。

采纳答案by Jon Skeet

A few comments on the answers given so far:

对迄今为止给出的答案的一些评论：

• Every single one of them (so far!) will fail on surrogate pairs and combining characters. Oh the joys of Unicode. Reversing a string isn't the same as reversing a sequence of chars.
• I like Marc's optimisationfor null, empty, and single character inputs. In particular, not only does this get the right answer quickly, but it also handles null (which none of the other answers do)
• I originally thought that ToCharArrayfollowed by Array.Reversewould be the fastest, but it does create one "garbage" copy.
• The StringBuildersolution creates a single string (not char array) and manipulates that until you call ToString. There's no extra copying involved... but there's a lot more work maintaining lengths etc.

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

Which is the more efficient solution? Well, I'd have to benchmark it to have any idea at all - but even so that's not going to tell the whole story. Are you using this in a situation with high memory pressure, where extra garbage is a real pain? How fast is your memory vs your CPU, etc?

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

As ever, readability is usuallyking - and it doesn't get much better than Marc's answer on that front. In particular, there's no roomfor an off-by-one error, whereas I'd have to actually put some thought into validating the other answers. I don't like thinking. It hurts my brain, so I try not to do it very often. Using the built-in Array.Reversesounds much better to me. (Okay, so it still fails on surrogates etc, but hey...)

与以往一样，可读性通常是至高无上的——在这方面，它并没有比 Marc 的答案好多少。特别是，没有一个错误的余地，而我实际上必须考虑验证其他答案。我不喜欢思考。它伤害了我的大脑，所以我尽量不经常这样做。使用内置的Array.Reverse声音对我来说好多了。（好吧，所以它在代理等方面仍然失败，但是嘿......）

回答by Mehrdad Afshari

Since strings are immutable, each +=statement will create a new string by copying the string in the last step, along with the single character to form a new string. Effectively, this will be an O(n²) algorithm instead of O(n).

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

A faster way would be (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);
}

回答by Marc Gravell

Most importantly? That will suck performance wise - it has to create lotsof strings (one per character). The simplest way is something like:

最重要的是？这会降低性能 - 它必须创建大量字符串（每个字符一个）。最简单的方法是这样的：

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);
}

回答by Garry Shutler

The problem is that string concatenations are expensive to do as strings are immutable in C#. The example given will create a new string one character longer each iteration which is very inefficient. To avoid this you should use the StringBuilderclass instead like so:

问题是字符串连接的开销很大，因为字符串在 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();
}

The StringBuilder is written specifically for scenarios like this as it gives you the ability to concatenate strings without the drawback of excessive memory allocation.

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

You will notice I have provided the StringBuilder with an initial capacity which you don't often see. As you know the length of the result to begin with, this removes needless memory allocations.

您会注意到我为 StringBuilder 提供了一个您不经常看到的初始容量。正如您知道开始的结果长度，这消除了不必要的内存分配。

What normally happens is it allocates an amount of memory to the StringBuilder (default 16 characters). Once the contents attempts to exceed that capacity it doubles (I think) its own capactity and carries on. This is much better than allocating memory each time as would happen with normal strings, but if you can avoid this as well it's even better.

通常发生的是它为 StringBuilder 分配一定数量的内存（默认为 16 个字符）。一旦内容试图超过该容量，它就会将（我认为）自己的容量加倍并继续进行。这比普通字符串每次分配内存要好得多，但如果您也可以避免这种情况，那就更好了。

回答by chris.w.mclean

Better way to tackle it would be to use a StringBuilder, since it is not immutable you won't get the terrible object generation behavior that you would get above. In .net all strings are immutable, which means that the += operator there will create a new object each time it is hit. StringBuilder uses an internal buffer, so the reversal could be done in the buffer w/ no extra object allocations.

解决它的更好方法是使用 StringBuilder，因为它不是一成不变的，你不会得到你会遇到的可怕的对象生成行为。在 .net 中，所有字符串都是不可变的，这意味着 += 运算符每次被命中时都会创建一个新对象。StringBuilder 使用内部缓冲区，因此可以在缓冲区中完成反转，无需额外的对象分配。

回答by Charlie

You should use the StringBuilder class to create your resulting string. A string is immutable so when you append a string in each interation of the loop, a new string has to be created, which isn't very efficient.

您应该使用 StringBuilder 类来创建结果字符串。字符串是不可变的，因此当您在循环的每次交互中附加一个字符串时，必须创建一个新字符串，这不是很有效。

回答by jasonh

You can do this in .NET 3.5 instead:

您可以在 .NET 3.5 中执行此操作：

    public static string Reverse(this string s)
    {
        return new String((s.ToCharArray().Reverse()).ToArray());
    }

回答by JohnP

I prefer something like this:

我更喜欢这样的事情：

using System;
using System.Text;
namespace SpringTest3
{
    static class Extentions
    {
        static private StringBuilder ReverseStringImpl(string s, int pos, StringBuilder sb)
        {
            return (s.Length <= --pos || pos < 0) ? sb : ReverseStringImpl(s, pos, sb.Append(s[pos]));
        }

        static public string Reverse(this string s)
        {
            return ReverseStringImpl(s, s.Length, new StringBuilder()).ToString();
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("abc".Reverse());
        }
    }
}

回答by Sandeep

x is the string to reverse.

x 是要反转的字符串。

        Stack<char> stack = new Stack<char>(x);

        string s = new string(stack.ToArray());

回答by Ryan Graham

This method cuts the number of iterations in half. Rather than starting from the end, it starts from the beginning and swaps characters until it hits center. Had to convert the string to a char array because the indexer on a string has no setter.

这种方法将迭代次数减少了一半。它不是从末尾开始，而是从头开始并交换字符直到它到达中心。必须将字符串转换为字符数组，因为字符串上的索引器没有设置器。

    public string Reverse(String value)
    {
        if (String.IsNullOrEmpty(value)) throw new ArgumentNullException("value");

        char[] array = value.ToCharArray();

        for (int i = 0; i < value.Length / 2; i++)
        {
            char temp = array[i];
            array[i] = array[(array.Length - 1) - i];
            array[(array.Length - 1) - i] = temp;
        }

        return new string(array);
    }