一个更快的反转字符串的方法？

Question

一个更快的反转字符串的方法？

3

以下是我能创建的最快的反转字符串的代码。

public static void ReverseFast(string x)
{
    string text = x;
    StringBuilder reverse = new StringBuilder();

    for (int i = text.Length - 1; i >= 0; i--)
    {
        reverse.Append(text[i]);
    }
      Console.WriteLine(reverse);
}

我希望解决此方程中的每个瓶颈，使其尽可能快。到目前为止，我只发现了部分理解的数组边界检查是唯一的瓶颈。是否有任何方法可以禁用它？如果您使用.Length，编译器将决定不检查边界，但如果像我在for循环中递减，它仍然会进行边界检查吗？有人能把这个转换成使用指针的方式，从而避免边界检查吗？我想测试100k+字符范围内字符串速度差异。

根据下面的评论和帖子，这是我迄今为止想出的。

public static void ReverseFast(string x)
{
    StringBuilder reverse = new StringBuilder(x.Length);
    for (int i = x.Length - 1; i >= 0; i--)
    {
        reverse.Append(x[i]);
    }
    Console.WriteLine(reverse);
}

上述解决方案比建议的重复问题答案快得多。这个问题实际上是针对5000 * 26个字符范围内的反转。我仍然希望使用指针进行测试，以查看是否存在瓶颈，特别是在如此大量的字符情况下。

- CodeCamper

4

这绝不会成为你的瓶颈。说真的。 - It'sNotALie.

使用正确的长度（text.Length）初始化StringBuilder - 这将防止缓冲区被重新调整大小。 - JeffRSon

我的问题有点想探索C#中的指针替代方案，并批评我的当前想法。 - CodeCamper

用new StringBuilder(text.Length)替换new StringBuilder()可以消除所有不必要的内存[重新]分配。 - GSerg

在重复的问题中，此答案提供了一个使用指针的解决方案。不要止步于那里的被接受的答案，浏览所有答案。虽然对于大字符串，您可能需要删除stackalloc。 - GSerg

3个回答

4

这里提供一种基于指针的解决方案：

unsafe String Reverse(String s)
        {
            char[] sarr = new char[s.Length];
            int idx = s.Length;
            fixed (char* c = s)
            {
                char* c1 = c;
                while (idx != 0)
                {
                    sarr[--idx] = *c1++;
                }
            }

            return new String(sarr);
        }

去掉数组索引（sarr [ - - idx ]）后面的内容可能会更快：

unsafe String Reverse(String s)
        {
            char[] sarr = new char[s.Length];
            fixed (char* c = s)
            fixed (char* d = sarr)
            {
                char* c1 = c;
                char* d1 = d + s.Length;
                while (d1 > d)
                {
                    *--d1 = *c1++;
                }
            }

            return new String(sarr);
        }

- JeffRSon

不错的方法；我进行了基准测试，它仍然比平坦的 Array.Reverse 稍慢 - 我不敢说我知道为什么；但非常好。 - Marc Gravell

编辑：澄清一下 - 这似乎取决于字符串长度；对于小字符串，Array.Reverse 稍微快一点；对于大字符串，指针代码稍微快一点 - 差异不足以让我说哪个是明显的赢家。 - Marc Gravell

我不喜欢基于索引的数组访问，因为这涉及每次添加指针 - 现在只有指针... - JeffRSon

2

在创建StringBuilder时设置容量，这样它就不需要在循环过程中增长并分配更多内存。将参数赋值给本地变量是一个不必要的步骤，因为参数已经是本地变量。

public static void ReverseFast(string text) {
  StringBuilder reverse = new StringBuilder(text.Length);
  for (int i = text.Length - 1; i >= 0; i--) {
    reverse.Append(text[i]);
  }
}

这只是去除任何不必要工作的基本步骤。如果您真的在代码中遇到性能问题，您需要分析生成的代码所做的事情，并可能创建不同版本，根据当前框架和硬件执行不同的操作。

- Guffa

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Marc Gravell · Accepted Answer

var arr = x.ToCharArray();
Array.Reverse(arr);
return new string(arr);

请注意，这将反转任何Unicode修饰字符（重音符号等）。

基准测试：

Array.Reverse: 179ms
StringBuilder: 475ms

使用：

static void Main()
{
    string text = new string('x', 100000);
    GC.Collect();
    GC.WaitForPendingFinalizers();
    var watch = Stopwatch.StartNew();
    const int LOOP = 1000;
    for (int i = 0; i < LOOP; i++)
    {
        var arr = text.ToCharArray();
        Array.Reverse(arr);
        string y = new string(arr);
    }
    watch.Stop();
    Console.WriteLine("Array.Reverse: {0}ms", watch.ElapsedMilliseconds);

    GC.Collect();
    GC.WaitForPendingFinalizers();
    watch = Stopwatch.StartNew();
    for (int i = 0; i < LOOP; i++)
    {
        var reverse = new StringBuilder(text.Length);
        for (int j = text.Length - 1; j >= 0; j--)
        {
            reverse.Append(text[j]);
        }
        string y = reverse.ToString();
    }
    watch.Stop();
    Console.WriteLine("StringBuilder: {0}ms", watch.ElapsedMilliseconds);
}

如果我们尝试一个长度为500的字符串，并循环500000次：

Array.Reverse: 480ms
StringBuilder: 1176ms

我也尝试将 unsafe 添加到其中，即：

fixed (char* c = text)
{
    for (int j = text.Length - 1; j >= 0; j--)
    {
        reverse.Append(c[j]);
    }
}

这毫无影响。

我也添加了JeffRSon的答案；我得到：

Array.Reverse: 459ms
StringBuilder: 1092ms
Pointer: 513ms

(对于500长度x5000次迭代测试)