logo标签列表

反转字符串的最佳方法

c#.netperformancealgorithmunicode
570

我刚刚不得不在C# 2.0中编写一个字符串反转函数（即LINQ不可用），并得出了以下结果：

public string Reverse(string text)
{
    char[] cArray = text.ToCharArray();
    string reverse = String.Empty;
    for (int i = cArray.Length - 1; i > -1; i--)
    {
        reverse += cArray[i];
    }
    return reverse;
}

就我个人而言，我并不热衷于这个函数，并且确信有更好的方法来完成它。有吗？

63
如果您想获得适当的国际支持，翻译可能会非常棘手。例如，克罗地亚语/塞尔维亚语有两个字符的字母“lj”、“nj”等。 “ljudi”的正确反转应该是“idulj”，而不是“idujl”。当涉及到阿拉伯语、泰语等语言时，情况可能更加复杂。 - dbkk
2
我想知道将字符串连接起来是否比初始化临时数组并将结果存储在其中再将其转换为字符串更慢？ - The Muffin Man
4
较新的相关帖子：如何反转带有重音字符的字符串？ - Jeppe Stig Nielsen
15
请问您所说的“最好”是指什么？速度最快？可读性最高？在多种情况下（如空值检查、多语言等）最可靠？在不同版本的C＃和.NET中最易维护？ - hypehuman
5
为什么没有内置的直接方法来完成这个简单的任务？ - Krishnadas PC
53个回答
15

如果你想玩一个非常危险的游戏，那么这绝对是最快的方法（比 Array.Reverse 方法快大约四倍）。它是使用指针的原地反转。

请注意，我真的不建议在任何情况下使用此方法（在这里看一些不应该使用此方法的原因），但有趣的是可以看到它是可以做到的，而且一旦打开了不安全代码，字符串就不是真正的不可变的。

public static unsafe string Reverse(string text)
{
    if (string.IsNullOrEmpty(text))
    {
        return text;
    }

    fixed (char* pText = text)
    {
        char* pStart = pText;
        char* pEnd = pText + text.Length - 1;
        for (int i = text.Length / 2; i >= 0; i--)
        {
            char temp = *pStart;
            *pStart++ = *pEnd;
            *pEnd-- = temp;
        }

        return text;
    }
}
1
我非常确定这将为utf16字符串返回不正确的结果，这真的会带来麻烦 :) - Sam Saffron
1
嗨，您应该链接到此https://dev59.com/T0XRa4cB1Zd3GeqPs5bh上的帖子，就像我之前所说的那样，这真的很麻烦... - Sam Saffron
1
这可能完全是邪恶和不明智的（正如您自己所承认的那样），但仍然有一种高性能的方法可以使用unsafe代码来反转字符串，这种方法并不邪恶，并且在许多情况下仍然优于Array.Reverse。看看我的答案。 - Dan Tao
14

首先，您不需要调用ToCharArray，因为字符串已经可以像字符数组一样索引，这将节省您的内存分配。

下一个优化是使用StringBuilder来防止不必要的内存分配（因为字符串是不可变的，每次连接它们都会复制一份字符串）。为了进一步优化，我们预设StringBuilder的长度，这样它就不需要扩展其缓冲区。

public string Reverse(string text)
{
    if (string.IsNullOrEmpty(text))
    {
        return text;
    }

    StringBuilder builder = new StringBuilder(text.Length);
    for (int i = text.Length - 1; i >= 0; i--)
    {
        builder.Append(text[i]);
    }

    return builder.ToString();
}

编辑：性能数据

我用以下简单程序测试了这个函数和使用 Array.Reverse 的函数，其中 Reverse1 是一个函数，Reverse2 是另一个函数：

static void Main(string[] args)
{
    var text = "abcdefghijklmnopqrstuvwxyz";

    // pre-jit
    text = Reverse1(text); 
    text = Reverse2(text);

    // test
    var timer1 = Stopwatch.StartNew();
    for (var i = 0; i < 10000000; i++)
    {
        text = Reverse1(text);
    }

    timer1.Stop();
    Console.WriteLine("First: {0}", timer1.ElapsedMilliseconds);

    var timer2 = Stopwatch.StartNew();
    for (var i = 0; i < 10000000; i++)
    {
        text = Reverse2(text);
    }

    timer2.Stop();
    Console.WriteLine("Second: {0}", timer2.ElapsedMilliseconds);

    Console.ReadLine();
}

事实证明，对于短字符串而言，Array.Reverse 方法的速度大约是上述方法的两倍，对于长字符串来说，差距更加显著。因此，考虑到 Array.Reverse 方法更为简单和快速，我建议您使用该方法而非上述方法。我将其保留在这里只是为了表明这不是您应该采用的方式（令我大感意外！）。

将text.Length存储在变量中，是否会提高一些速度，因为您是通过对象引用它的？ - David Robbins
12

尝试使用Array.Reverse


public string Reverse(string str)
{
    char[] array = str.ToCharArray();
    Array.Reverse(array);
    return new string(array);
}
无法处理许多其他事情中的组合代码点。 - Mooing Duck
@MooingDuck 我查了一下代码点。是的，你是正确的。它不能处理代码点。对于这样一个看起来很简单的问题，确定所有要求是很困难的。感谢您的反馈。 - Mike Two
12

“最好”的定义因情况而异，但以下是几个从快到慢排列的简短替代品：

string s = "z̽a̎l͘g̈o̓", pattern = @"(?s).(?<=(?:.(?=.*$(?<=((\P{M}\p{C}?\p{M}*)\1?))))*)";

string s1 = string.Concat(s.Reverse());                          // "☐☐̓ög͘l̎a̽z"  

string s2 = Microsoft.VisualBasic.Strings.StrReverse(s);         // "o̓g̈l͘a̎̽z"  

string s3 = string.Concat(StringInfo.ParseCombiningCharacters(s).Reverse()
    .Select(i => StringInfo.GetNextTextElement(s, i)));          // "o̓g̈l͘a̎z̽"  

string s4 = Regex.Replace(s, pattern, "$2").Remove(s.Length);    // "o̓g̈l͘a̎z̽"
10
public static string Reverse(string input)
{
    return string.Concat(Enumerable.Reverse(input));
}

当然可以使用Reverse方法扩展字符串类

public static class StringExtensions
{
    public static string Reverse(this string input)
    {
        return string.Concat(Enumerable.Reverse(input));
    }
}
Enumerable.Reverse(input) is equal to input.Reverse() - fubo
7

很抱歉文章有点长，但这可能会很有趣。

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        public static string ReverseUsingArrayClass(string text)
        {
            char[] chars = text.ToCharArray();
            Array.Reverse(chars);
            return new string(chars);
        }

        public static string ReverseUsingCharacterBuffer(string text)
        {
            char[] charArray = new char[text.Length];
            int inputStrLength = text.Length - 1;
            for (int idx = 0; idx <= inputStrLength; idx++) 
            {
                charArray[idx] = text[inputStrLength - idx];                
            }
            return new string(charArray);
        }

        public static string ReverseUsingStringBuilder(string text)
        {
            if (string.IsNullOrEmpty(text))
            {
                return text;
            }

            StringBuilder builder = new StringBuilder(text.Length);
            for (int i = text.Length - 1; i >= 0; i--)
            {
                builder.Append(text[i]);
            }

            return builder.ToString();
        }

        private static string ReverseUsingStack(string input)
        {
            Stack<char> resultStack = new Stack<char>();
            foreach (char c in input)
            {
                resultStack.Push(c);
            }

            StringBuilder sb = new StringBuilder();
            while (resultStack.Count > 0)
            {
                sb.Append(resultStack.Pop());
            }
            return sb.ToString();
        }

        public static string ReverseUsingXOR(string text)
        {
            char[] charArray = text.ToCharArray();
            int length = text.Length - 1;
            for (int i = 0; i < length; i++, length--)
            {
                charArray[i] ^= charArray[length];
                charArray[length] ^= charArray[i];
                charArray[i] ^= charArray[length];
            }

            return new string(charArray);
        }


        static void Main(string[] args)
        {
            string testString = string.Join(";", new string[] {
                new string('a', 100), 
                new string('b', 101), 
                new string('c', 102), 
                new string('d', 103),                                                                   
            });
            int cycleCount = 100000;

            Stopwatch stopwatch = new Stopwatch();
            stopwatch.Start();
            for (int i = 0; i < cycleCount; i++) 
            {
                ReverseUsingCharacterBuffer(testString);
            }
            stopwatch.Stop();
            Console.WriteLine("ReverseUsingCharacterBuffer: " + stopwatch.ElapsedMilliseconds + "ms");

            stopwatch.Reset();
            stopwatch.Start();
            for (int i = 0; i < cycleCount; i++) 
            {
                ReverseUsingArrayClass(testString);
            }
            stopwatch.Stop();
            Console.WriteLine("ReverseUsingArrayClass: " + stopwatch.ElapsedMilliseconds + "ms");

            stopwatch.Reset();
            stopwatch.Start();
            for (int i = 0; i < cycleCount; i++) 
            {
                ReverseUsingStringBuilder(testString);
            }
            stopwatch.Stop();
            Console.WriteLine("ReverseUsingStringBuilder: " + stopwatch.ElapsedMilliseconds + "ms");

            stopwatch.Reset();
            stopwatch.Start();
            for (int i = 0; i < cycleCount; i++) 
            {
                ReverseUsingStack(testString);
            }
            stopwatch.Stop();
            Console.WriteLine("ReverseUsingStack: " + stopwatch.ElapsedMilliseconds + "ms");

            stopwatch.Reset();
            stopwatch.Start();
            for (int i = 0; i < cycleCount; i++) 
            {
                ReverseUsingXOR(testString);
            }
            stopwatch.Stop();
            Console.WriteLine("ReverseUsingXOR: " + stopwatch.ElapsedMilliseconds + "ms");            
        }
    }
}

结果：

  • 使用字符缓冲区进行反转：346毫秒
  • 使用数组类进行反转：87毫秒
  • 使用字符串构建器进行反转：824毫秒
  • 使用栈进行反转：2086毫秒
  • 使用异或进行反转：319毫秒
我在我的帖子中添加了一个类似的比较，这是一个社区维基，所以您应该能够进行编辑。性能取决于字符串的长度和算法，绘制成图表会很有趣。我仍然认为Array.Reverse在所有情况下都是最快的。 - Sam Saffron
当神奇的TrySZReverse函数（它在反转实现中使用）失败时，Array.Reverse会回退到涉及装箱的简单实现，因此我的方法将在所有情况下都是最快的。但我不知道什么条件会使TrySZReverse失败。 - aku
结果证明，并非在所有情况下都是最快的：），我更新了我的帖子。这仍然需要使用Unicode进行正确性和速度测试。 - Sam Saffron
7

不需要使用函数，直接在原地修改即可。注意：在某些VS版本的Immediate窗口中，第二行代码会抛出一个参数异常。

string s = "Blah";
s = new string(s.ToCharArray().Reverse().ToArray());
这并不是真正的就地操作，因为你正在创建一个“新字符串”。 - mbadawi23
6
public string Reverse(string input)
{
    char[] output = new char[input.Length];

    int forwards = 0;
    int backwards = input.Length - 1;

    do
    {
        output[forwards] = input[backwards];
        output[backwards] = input[forwards];
    }while(++forwards <= --backwards);

    return new String(output);
}

public string DotNetReverse(string input)
{
    char[] toReverse = input.ToCharArray();
    Array.Reverse(toReverse);
    return new String(toReverse);
}

public string NaiveReverse(string input)
{
    char[] outputArray = new char[input.Length];
    for (int i = 0; i < input.Length; i++)
    {
        outputArray[i] = input[input.Length - 1 - i];
    }

    return new String(outputArray);
}    

public string RecursiveReverse(string input)
{
    return RecursiveReverseHelper(input, 0, input.Length - 1);
}

public string RecursiveReverseHelper(string input, int startIndex , int endIndex)
{
    if (startIndex == endIndex)
    {
        return "" + input[startIndex];
    }

    if (endIndex - startIndex == 1)
    {
        return "" + input[endIndex] + input[startIndex];
    }

    return input[endIndex] + RecursiveReverseHelper(input, startIndex + 1, endIndex - 1) + input[startIndex];
}


void Main()
{
    int[] sizes = new int[] { 10, 100, 1000, 10000 };
    for(int sizeIndex = 0; sizeIndex < sizes.Length; sizeIndex++)
    {
        string holaMundo  = "";
        for(int i = 0; i < sizes[sizeIndex]; i+= 5)
        {   
            holaMundo += "ABCDE";
        }

        string.Format("\n**** For size: {0} ****\n", sizes[sizeIndex]).Dump();

        string odnuMaloh = DotNetReverse(holaMundo);

        var stopWatch = Stopwatch.StartNew();
        string result = NaiveReverse(holaMundo);
        ("Naive Ticks: " + stopWatch.ElapsedTicks).Dump();

        stopWatch.Restart();
        result = Reverse(holaMundo);
        ("Efficient linear Ticks: " + stopWatch.ElapsedTicks).Dump();

        stopWatch.Restart();
        result = RecursiveReverse(holaMundo);
        ("Recursive Ticks: " + stopWatch.ElapsedTicks).Dump();

        stopWatch.Restart();
        result = DotNetReverse(holaMundo);
        ("DotNet Reverse Ticks: " + stopWatch.ElapsedTicks).Dump();
    }
}

输出

对于大小为10的情况

Naive Ticks: 1
Efficient linear Ticks: 0
Recursive Ticks: 2
DotNet Reverse Ticks: 1

对于尺寸：100

Naive Ticks: 2
Efficient linear Ticks: 1
Recursive Ticks: 12
DotNet Reverse Ticks: 1

对于大小：1000

Naive Ticks: 5
Efficient linear Ticks: 2
Recursive Ticks: 358
DotNet Reverse Ticks: 9

对于大小为10000的情况

Naive Ticks: 32
Efficient linear Ticks: 28
Recursive Ticks: 84808
DotNet Reverse Ticks: 33
1
需要在 Reverse(...) 中检查空字符串。否则，工作做得很好。 - user1908746
5

最简单的方法：

string reversed = new string(text.Reverse().ToArray());
4
如何考虑：
    private string Reverse(string stringToReverse)
    {
        char[] rev = stringToReverse.Reverse().ToArray();
        return new string(rev); 
    }
与上述其他方法一样存在相同的代码点问题，并且执行速度比先使用 ToCharArray 慢得多。LINQ 枚举器也比 Array.Reverse() 慢得多。 - Abel
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接