Najlepszy sposób na odwrócenie łańcucha

Właśnie musiałem napisać funkcję odwrotną do napisów w C # 2.0 (tj. LINQ niedostępny) i wymyśliłem to:

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

Osobiście nie jestem szalony z powodu tej funkcji i jestem przekonany, że jest lepszy sposób, aby to zrobić. Jest tu?

public static string Reverse( string s )
{
    char[] charArray = s.ToCharArray();
    Array.Reverse( charArray );
    return new string( charArray );
}

Tutaj rozwiązanie, które poprawnie odwraca ciąg "Les Mise\u0301rables"jako "selbare\u0301siM seL". Powinno to być renderowane podobnie selbarésiM seL, a nie selbaŕesiM seL(zwróć uwagę na położenie akcentu), jak wynikałoby to z większości implementacji opartych na jednostkach kodu ( Array.Reverseitp.), A nawet na punktach kodu (odwracanie ze szczególnym uwzględnieniem par zastępczych).

using System;
using System.Collections.Generic;
using System.Globalization;
using System.Linq;

public static class Test
{
    private static IEnumerable<string> GraphemeClusters(this string s) {
        var enumerator = StringInfo.GetTextElementEnumerator(s);
        while(enumerator.MoveNext()) {
            yield return (string)enumerator.Current;
        }
    }
    private static string ReverseGraphemeClusters(this string s) {
        return string.Join("", s.GraphemeClusters().Reverse().ToArray());
    }

    public static void Main()
    {
        var s = "Les Mise\u0301rables";
        var r = s.ReverseGraphemeClusters();
        Console.WriteLine(r);
    }
}

(I przykład biegania na żywo tutaj: https://ideone.com/DqAeMJ )

Po prostu używa interfejsu API .NET do iteracji klastra grafem , który istnieje tam od zawsze, ale wydaje się nieco „ukryty”.

To okazuje się zaskakująco trudne pytanie.

Polecam używanie Array.Reverse w większości przypadków, ponieważ jest on kodowany natywnie i jest bardzo prosty w utrzymaniu i zrozumieniu.

Wydaje się, że przewyższa StringBuilder we wszystkich testowanych przypadkach.

public string Reverse(string text)
{
   if (text == null) return null;

   // this was posted by petebob as well 
   char[] array = text.ToCharArray();
   Array.Reverse(array);
   return new String(array);
}

Istnieje drugie podejście, które może być szybsze dla niektórych długości łańcucha, które używa Xor .

    public static string ReverseXor(string s)
    {
        if (s == null) return null;
        char[] charArray = s.ToCharArray();
        int len = s.Length - 1;

        for (int i = 0; i < len; i++, len--)
        {
            charArray[i] ^= charArray[len];
            charArray[len] ^= charArray[i];
            charArray[i] ^= charArray[len];
        }

        return new string(charArray);
    }

Uwaga Jeśli chcesz obsługiwać pełny zestaw znaków Unicode UTF16, przeczytaj to . I zamiast tego użyj tam implementacji. Można go dalej zoptymalizować za pomocą jednego z powyższych algorytmów i przebiegając przez ciąg znaków, aby wyczyścić go po odwróceniu znaków.

Oto porównanie wydajności metod StringBuilder, Array.Reverse i Xor.

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

namespace ConsoleApplication4
{
    class Program
    {
        delegate string StringDelegate(string s);

        static void Benchmark(string description, StringDelegate d, int times, string text)
        {
            Stopwatch sw = new Stopwatch();
            sw.Start();
            for (int j = 0; j < times; j++)
            {
                d(text);
            }
            sw.Stop();
            Console.WriteLine("{0} Ticks {1} : called {2} times.", sw.ElapsedTicks, description, times);
        }

        public static string ReverseXor(string s)
        {
            char[] charArray = s.ToCharArray();
            int len = s.Length - 1;

            for (int i = 0; i < len; i++, len--)
            {
                charArray[i] ^= charArray[len];
                charArray[len] ^= charArray[i];
                charArray[i] ^= charArray[len];
            }

            return new string(charArray);
        }

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

        public static string ReverseArray(string text)
        {
            char[] array = text.ToCharArray();
            Array.Reverse(array);
            return (new string(array));
        }

        public static string StringOfLength(int length)
        {
            Random random = new Random();
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < length; i++)
            {
                sb.Append(Convert.ToChar(Convert.ToInt32(Math.Floor(26 * random.NextDouble() + 65))));
            }
            return sb.ToString();
        }

        static void Main(string[] args)
        {

            int[] lengths = new int[] {1,10,15,25,50,75,100,1000,100000};

            foreach (int l in lengths)
            {
                int iterations = 10000;
                string text = StringOfLength(l);
                Benchmark(String.Format("String Builder (Length: {0})", l), ReverseSB, iterations, text);
                Benchmark(String.Format("Array.Reverse (Length: {0})", l), ReverseArray, iterations, text);
                Benchmark(String.Format("Xor (Length: {0})", l), ReverseXor, iterations, text);

                Console.WriteLine();    
            }

            Console.Read();
        }
    }
}

Oto wyniki:

26251 Ticks String Builder (Length: 1) : called 10000 times.
33373 Ticks Array.Reverse (Length: 1) : called 10000 times.
20162 Ticks Xor (Length: 1) : called 10000 times.

51321 Ticks String Builder (Length: 10) : called 10000 times.
37105 Ticks Array.Reverse (Length: 10) : called 10000 times.
23974 Ticks Xor (Length: 10) : called 10000 times.

66570 Ticks String Builder (Length: 15) : called 10000 times.
26027 Ticks Array.Reverse (Length: 15) : called 10000 times.
24017 Ticks Xor (Length: 15) : called 10000 times.

101609 Ticks String Builder (Length: 25) : called 10000 times.
28472 Ticks Array.Reverse (Length: 25) : called 10000 times.
35355 Ticks Xor (Length: 25) : called 10000 times.

161601 Ticks String Builder (Length: 50) : called 10000 times.
35839 Ticks Array.Reverse (Length: 50) : called 10000 times.
51185 Ticks Xor (Length: 50) : called 10000 times.

230898 Ticks String Builder (Length: 75) : called 10000 times.
40628 Ticks Array.Reverse (Length: 75) : called 10000 times.
78906 Ticks Xor (Length: 75) : called 10000 times.

312017 Ticks String Builder (Length: 100) : called 10000 times.
52225 Ticks Array.Reverse (Length: 100) : called 10000 times.
110195 Ticks Xor (Length: 100) : called 10000 times.

2970691 Ticks String Builder (Length: 1000) : called 10000 times.
292094 Ticks Array.Reverse (Length: 1000) : called 10000 times.
846585 Ticks Xor (Length: 1000) : called 10000 times.

305564115 Ticks String Builder (Length: 100000) : called 10000 times.
74884495 Ticks Array.Reverse (Length: 100000) : called 10000 times.
125409674 Ticks Xor (Length: 100000) : called 10000 times.

Wydaje się, że Xor może być szybszy w przypadku krótkich łańcuchów.

Jeśli możesz użyć LINQ (.NET Framework 3.5+), to zastosowanie jednej linijki da ci krótki kod. Nie zapomnij dodać, using System.Linq;aby mieć dostęp do Enumerable.Reverse:

public string ReverseString(string srtVarable)
{
    return new string(srtVarable.Reverse().ToArray());
}

Uwagi:

• nie najszybsza wersja - według Martina Niederla 5,7 razy wolniejsza niż najszybszy wybór tutaj.
• ten kod, podobnie jak wiele innych opcji, całkowicie ignoruje wszelkiego rodzaju kombinacje wieloznakowe, więc ogranicz użycie do zadań domowych i ciągów znaków, które nie zawierają takich znaków. Zobacz inną odpowiedź w tym pytaniu dotyczącą implementacji, która poprawnie obsługuje takie kombinacje.

Jeśli ciąg zawiera dane Unicode (ściśle mówiąc, znaki inne niż BMP), inne opublikowane metody spowodują jego uszkodzenie, ponieważ podczas odwracania ciągu nie można zamienić kolejności wysokich i niskich jednostek kodu zastępczego. (Więcej informacji na ten temat można znaleźć na moim blogu ).

Poniższy przykładowy kod poprawnie odwróci ciąg znaków, który zawiera znaki inne niż BMP, np. „\ U00010380 \ U00010381” (litera Ugaritic Alpa, litera Ugaritic Beta).

public static string Reverse(this string input)
{
    if (input == null)
        throw new ArgumentNullException("input");

    // allocate a buffer to hold the output
    char[] output = new char[input.Length];
    for (int outputIndex = 0, inputIndex = input.Length - 1; outputIndex < input.Length; outputIndex++, inputIndex--)
    {
        // check for surrogate pair
        if (input[inputIndex] >= 0xDC00 && input[inputIndex] <= 0xDFFF &&
            inputIndex > 0 && input[inputIndex - 1] >= 0xD800 && input[inputIndex - 1] <= 0xDBFF)
        {
            // preserve the order of the surrogate pair code units
            output[outputIndex + 1] = input[inputIndex];
            output[outputIndex] = input[inputIndex - 1];
            outputIndex++;
            inputIndex--;
        }
        else
        {
            output[outputIndex] = input[inputIndex];
        }
    }

    return new string(output);
}

Ok, w interesie „nie powtarzaj się”, oferuję następujące rozwiązanie:

public string Reverse(string text)
{
   return Microsoft.VisualBasic.Strings.StrReverse(text);
}

Rozumiem, że ta implementacja, domyślnie dostępna w VB.NET, poprawnie obsługuje znaki Unicode.

Greg Beech opublikował unsafeopcję, która jest rzeczywiście tak szybka, jak to możliwe (jest to odwrócenie w miejscu); ale, jak wskazał w swojej odpowiedzi, jest to całkowicie katastrofalny pomysł .

Powiedziałem, że jestem zaskoczony, że istnieje tak duży konsensus, że Array.Reversejest to najszybsza metoda. Nadal istnieje unsafepodejście, które zwraca odwróconą kopię łańcucha (brak shenaniganów odwracania w miejscu) znacznie szybciej niż Array.Reversemetoda dla małych łańcuchów:

public static unsafe string Reverse(string text)
{
    int len = text.Length;

    // Why allocate a char[] array on the heap when you won't use it
    // outside of this method? Use the stack.
    char* reversed = stackalloc char[len];

    // Avoid bounds-checking performance penalties.
    fixed (char* str = text)
    {
        int i = 0;
        int j = i + len - 1;
        while (i < len)
        {
            reversed[i++] = str[j--];
        }
    }

    // Need to use this overload for the System.String constructor
    // as providing just the char* pointer could result in garbage
    // at the end of the string (no guarantee of null terminator).
    return new string(reversed, 0, len);
}

Oto niektóre wyniki testów porównawczych .

Widać, że wzrost wydajności zmniejsza się, a następnie znika w stosunku do Array.Reversemetody, gdy ciągi stają się większe. Jednak w przypadku małych i średnich strun trudno jest pokonać tę metodę.

Łatwą i miłą odpowiedzią jest użycie metody rozszerzenia:

static class ExtentionMethodCollection
{
    public static string Inverse(this string @base)
    {
        return new string(@base.Reverse().ToArray());
    }
}

a oto wynik:

string Answer = "12345".Inverse(); // = "54321"

Jeśli chcesz zagrać w naprawdę niebezpieczną grę, jest to zdecydowanie najszybszy sposób (około cztery razy szybszy niż Array.Reversemetoda). To odwrotność na miejscu za pomocą wskaźników.

Zauważ, że tak naprawdę nigdy nie polecam tego do żadnego użytku ( spójrz tutaj z kilku powodów, dla których nie powinieneś używać tej metody ), ale po prostu interesujące jest to, że można to zrobić i że ciągi nie są niezmienne po włączeniu niebezpiecznego kodu.

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

Zobacz wpis na Wikipedii tutaj . Implementują metodę rozszerzenia String.Reverse. Pozwala to na napisanie takiego kodu:

string s = "olleh";
s.Reverse();

Używają także kombinacji ToCharArray / Reverse, którą sugerują inne odpowiedzi na to pytanie. Kod źródłowy wygląda następująco:

public static string Reverse(this string input)
{
    char[] chars = input.ToCharArray();
    Array.Reverse(chars);
    return new String(chars);
}

Po pierwsze, nie musisz dzwonić, ToCharArrayponieważ ciąg znaków może być już zindeksowany jako tablica znaków, dzięki czemu zaoszczędzisz przydział.

Następną optymalizacją jest użycie a, StringBuilderaby zapobiec niepotrzebnym przydziałom (ponieważ ciągi są niezmienne, ich łączenie tworzy kopię ciągu za każdym razem). Aby dalej to zoptymalizować, wstępnie ustawiliśmy długość, StringBuilderaby nie trzeba było rozszerzać bufora.

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

Edycja: Dane wydajności

Testowałem tę funkcję i funkcję za Array.Reversepomocą następującego prostego programu, w którym Reverse1jest jedna funkcja, a Reverse2druga:

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

Okazuje się, że dla krótkich łańcuchów Array.Reversemetoda jest około dwa razy szybsza niż powyższa, a dla dłuższych łańcuchów różnica jest jeszcze bardziej wyraźna. Biorąc pod uwagę, że Array.Reversemetoda jest zarówno prostsza, jak i szybsza, polecam jej użycie zamiast tej. Zostawiam to tutaj, aby pokazać, że nie jest to sposób, w jaki powinieneś to zrobić (ku mojemu zaskoczeniu!)

Spróbuj użyć Array.Reverse

public string Reverse(string str)
{
    char[] array = str.ToCharArray();
    Array.Reverse(array);
    return new string(array);
}

public static string Reverse(string input)
{
    return string.Concat(Enumerable.Reverse(input));
}

Oczywiście można rozszerzyć klasę łańcuchów za pomocą metody Reverse

public static class StringExtensions
{
    public static string Reverse(this string input)
    {
        return string.Concat(Enumerable.Reverse(input));
    }
}

„Najlepsze” może zależeć od wielu rzeczy, ale oto kilka krótkich alternatyw uporządkowanych od szybkiego do wolnego:

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̽"  👍

Począwszy od .NET Core 2.1 istnieje nowy sposób na odwrócenie łańcucha za pomocą string.Create metody.

Zauważ, że to rozwiązanie nie obsługuje poprawnie łączenia znaków Unicode itp., Ponieważ „Les Mise \ u0301rables” zostałby przekonwertowany na „selbarésiM seL”. Na pozostałe odpowiedzi dla lepszego rozwiązania.

public static string Reverse(string input)
{
    return string.Create<string>(input.Length, input, (chars, state) =>
    {
        state.AsSpan().CopyTo(chars);
        chars.Reverse();
    });
}

To zasadniczo kopiuje postacie input do nowego ciągu i odwraca nowy ciąg w miejscu.

Dlaczego jest string.Create użyteczny?

Kiedy tworzymy ciąg z istniejącej tablicy, przydzielana jest nowa tablica wewnętrzna i wartości są kopiowane. W przeciwnym razie byłoby możliwe zmutowanie łańcucha po jego utworzeniu (w bezpiecznym środowisku). Oznacza to, że w poniższym fragmencie musimy dwukrotnie przydzielić tablicę o długości 10, jedną jako bufor, a drugą jako wewnętrzną tablicę łańcucha.

var chars = new char[10];
// set array values
var str = new string(chars);

string.Createzasadniczo pozwala nam manipulować wewnętrzną tablicą podczas tworzenia łańcucha. Oznacza to, że nie potrzebujemy już bufora i dlatego możemy uniknąć przydzielenia tej tablicy znaków.

Steve Gordon napisał o tym bardziej szczegółowo tutaj . Jest też artykuł o MSDN .

Jak korzystać string.Create?

public static string Create<TState>(int length, TState state, SpanAction<char, TState> action);

Metoda przyjmuje trzy parametry:

1. Długość ciągu do utworzenia,
2. dane, których chcesz użyć do dynamicznego tworzenia nowego ciągu,
3. oraz delegat, który tworzy końcowy ciąg z danych, gdzie pierwszy parametr wskazuje na wewnętrzną chartablicę nowego ciągu, a drugi to dane (stan), które przekazałeś string.Create.

Wewnątrz delegata możemy określić sposób tworzenia nowego ciągu z danych. W naszym przypadku po prostu kopiujemy znaki ciągu wejściowego do Spanużywanego przez nowy ciąg. Następnie odwracamySpan a zatem cały ciąg znaków jest odwracany.

Benchmarki

Aby porównać mój proponowany sposób odwrócenia ciągu znaków z zaakceptowaną odpowiedzią, napisałem dwa testy porównawcze za pomocą BenchmarkDotNet.

public class StringExtensions
{
    public static string ReverseWithArray(string input)
    {
        var charArray = input.ToCharArray();
        Array.Reverse(charArray);
        return new string(charArray);
    }

    public static string ReverseWithStringCreate(string input)
    {
        return string.Create(input.Length, input, (chars, state) =>
        {
            state.AsSpan().CopyTo(chars);
            chars.Reverse();
        });
    }
}

[MemoryDiagnoser]
public class StringReverseBenchmarks
{
    private string input;

    [Params(10, 100, 1000)]
    public int InputLength { get; set; }


    [GlobalSetup]
    public void SetInput()
    {
        // Creates a random string of the given length
        this.input = RandomStringGenerator.GetString(InputLength);
    }

    [Benchmark(Baseline = true)]
    public string WithReverseArray() => StringExtensions.ReverseWithArray(input);

    [Benchmark]
    public string WithStringCreate() => StringExtensions.ReverseWithStringCreate(input);
}

Oto wyniki na moim komputerze:

| Method           | InputLength |         Mean |      Error |    StdDev |  Gen 0 | Allocated |
| ---------------- | ----------- | -----------: | ---------: | --------: | -----: | --------: |
| WithReverseArray | 10          |    45.464 ns |  0.4836 ns | 0.4524 ns | 0.0610 |      96 B |
| WithStringCreate | 10          |    39.749 ns |  0.3206 ns | 0.2842 ns | 0.0305 |      48 B |
|                  |             |              |            |           |        |           |
| WithReverseArray | 100         |   175.162 ns |  2.8766 ns | 2.2458 ns | 0.2897 |     456 B |
| WithStringCreate | 100         |   125.284 ns |  2.4657 ns | 2.0590 ns | 0.1473 |     232 B |
|                  |             |              |            |           |        |           |
| WithReverseArray | 1000        | 1,523.544 ns |  9.8808 ns | 8.7591 ns | 2.5768 |    4056 B |
| WithStringCreate | 1000        | 1,078.957 ns | 10.2948 ns | 9.6298 ns | 1.2894 |    2032 B |

Jak widać, ReverseWithStringCreateprzydzielamy tylko połowę pamięci używanej przez ReverseWithArraymetodę.

Nie przejmuj się funkcją, po prostu zrób to na miejscu. Uwaga: Druga linia wyrzuci wyjątek argumentu w oknie Natychmiastowe niektórych wersji VS.

string s = "Blah";
s = new string(s.ToCharArray().Reverse().ToArray()); 

Przepraszam za długi post, ale może to być interesujące

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

Wyniki:

• ReverseUsingCharacterBuffer: 346ms
• ReverseUsingArrayClass: 87ms
• ReverseUsingStringBuilder: 824ms
• ReverseUsingStack: 2086ms
• ReverseUsingXOR: 319ms

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

Wynik

Dla rozmiaru: 10

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

Dla rozmiaru: 100

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

Dla rozmiaru: 1000

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

Dla rozmiaru: 10000

Naive Ticks: 32
Efficient linear Ticks: 28
Recursive Ticks: 84808
DotNet Reverse Ticks: 33

Najprostszy sposób:

string reversed = new string(text.Reverse().ToArray());

Rozwiązanie oparte na stosie.

    public static string Reverse(string text)
    {
        var stack = new Stack<char>(text);
        var array = new char[stack.Count];

        int i = 0;
        while (stack.Count != 0)
        {
            array[i++] = stack.Pop();
        }

        return new string(array);
    }

Lub

    public static string Reverse(string text)
    {
        var stack = new Stack<char>(text);
        return string.Join("", stack);
    }

Musiałem przesłać rekurencyjny przykład:

private static string Reverse(string str)
{
    if (str.IsNullOrEmpty(str) || str.Length == 1)
        return str;
    else
        return str[str.Length - 1] + Reverse(str.Substring(0, str.Length - 1));
}

Co powiesz na:

    private string Reverse(string stringToReverse)
    {
        char[] rev = stringToReverse.Reverse().ToArray();
        return new string(rev); 
    }

Zrobiłem port C # z Microsoft.VisualBasic.Strings . Nie jestem pewien, dlaczego trzymają tak przydatne funkcje (z VB) poza System.String w Framework, ale nadal pod Microsoft.VisualBasic. Ten sam scenariusz dla funkcji finansowych (np Microsoft.VisualBasic.Financial.Pmt().).

public static string StrReverse(this string expression)
{
    if ((expression == null))
        return "";

    int srcIndex;

    var length = expression.Length;
    if (length == 0)
        return "";

    //CONSIDER: Get System.String to add a surrogate aware Reverse method

    //Detect if there are any graphemes that need special handling
    for (srcIndex = 0; srcIndex <= length - 1; srcIndex++)
    {
        var ch = expression[srcIndex];
        var uc = char.GetUnicodeCategory(ch);
        if (uc == UnicodeCategory.Surrogate || uc == UnicodeCategory.NonSpacingMark || uc == UnicodeCategory.SpacingCombiningMark || uc == UnicodeCategory.EnclosingMark)
        {
            //Need to use special handling
            return InternalStrReverse(expression, srcIndex, length);
        }
    }

    var chars = expression.ToCharArray();
    Array.Reverse(chars);
    return new string(chars);
}

///<remarks>This routine handles reversing Strings containing graphemes
/// GRAPHEME: a text element that is displayed as a single character</remarks>
private static string InternalStrReverse(string expression, int srcIndex, int length)
{
    //This code can only be hit one time
    var sb = new StringBuilder(length) { Length = length };

    var textEnum = StringInfo.GetTextElementEnumerator(expression, srcIndex);

    //Init enumerator position
    if (!textEnum.MoveNext())
    {
        return "";
    }

    var lastSrcIndex = 0;
    var destIndex = length - 1;

    //Copy up the first surrogate found
    while (lastSrcIndex < srcIndex)
    {
        sb[destIndex] = expression[lastSrcIndex];
        destIndex -= 1;
        lastSrcIndex += 1;
    }

    //Now iterate through the text elements and copy them to the reversed string
    var nextSrcIndex = textEnum.ElementIndex;

    while (destIndex >= 0)
    {
        srcIndex = nextSrcIndex;

        //Move to next element
        nextSrcIndex = (textEnum.MoveNext()) ? textEnum.ElementIndex : length;
        lastSrcIndex = nextSrcIndex - 1;

        while (lastSrcIndex >= srcIndex)
        {
            sb[destIndex] = expression[lastSrcIndex];
            destIndex -= 1;
            lastSrcIndex -= 1;
        }
    }

    return sb.ToString();
}

Przepraszamy za opublikowanie tego starego wątku. Ćwiczę kod do rozmowy kwalifikacyjnej.

Właśnie to wymyśliłem dla C #. Moja pierwsza wersja przed refaktoryzacją była okropna.

static String Reverse2(string str)
{
    int strLen = str.Length, elem = strLen - 1;
    char[] charA = new char[strLen];

    for (int i = 0; i < strLen; i++)
    {
        charA[elem] = str[i];
        elem--;
    }

    return new String(charA);
}

W przeciwieństwie do Array.Reverseponiższej metody, pojawia się szybciej z 12 lub mniej znakami w ciągu. Po 13 postaciach Array.Reversezaczyna się robić coraz szybciej i ostatecznie dość szybko dominuje. Chciałem tylko wskazać w przybliżeniu, gdzie prędkość zaczyna się zmieniać.

static String Reverse(string str)
{     
    char[] charA = str.ToCharArray();

    Array.Reverse(charA);

    return new String(charA);
}

Przy 100 znakach w ciągu jest on szybszy niż moja wersja x 4. Jednak gdybym wiedział, że ciągi zawsze będą miały mniej niż 13 znaków, użyłbym tego, który stworzyłem.

Testy zostały wykonane z Stopwatch5000000 iteracjami. Nie jestem też pewien, czy moja wersja obsługuje Surogaty czy kombinacje sytuacji znaków z Unicodekodowaniem.

„Lepszy sposób” zależy od tego, co jest dla Ciebie ważniejsze w Twojej sytuacji, wydajności, elegancji, łatwości konserwacji itp.

Tak czy inaczej, oto podejście z użyciem Array.Reverse:

string inputString="The quick brown fox jumps over the lazy dog.";
char[] charArray = inputString.ToCharArray(); 
Array.Reverse(charArray); 

string reversed = new string(charArray);

Jeśli kiedykolwiek pojawił się w wywiadzie i powiedziano ci, że nie możesz używać Array. Odwrotnie, myślę, że może to być jeden z najszybszych. Nie tworzy nowych ciągów i iteruje tylko ponad połowę tablicy (tj. Iteracje O (n / 2))

    public static string ReverseString(string stringToReverse)
    {
        char[] charArray = stringToReverse.ToCharArray();
        int len = charArray.Length-1;
        int mid = len / 2;

        for (int i = 0; i < mid; i++)
        {
            char tmp = charArray[i];
            charArray[i] = charArray[len - i];
            charArray[len - i] = tmp;
        }
        return new string(charArray);
    }

Jeśli masz ciąg znaków, który zawiera tylko znaki ASCII, możesz użyć tej metody.

    public static string ASCIIReverse(string s)
    {
        byte[] reversed = new byte[s.Length];

        int k = 0;
        for (int i = s.Length - 1; i >= 0; i--)
        {
            reversed[k++] = (byte)s[i];
        }

        return Encoding.ASCII.GetString(reversed);
    }

Przede wszystkim musisz zrozumieć, że str + = zmieni rozmiar pamięci łańcuchowej, aby zwolnić miejsce na 1 dodatkowy znak. To dobrze, ale jeśli masz, powiedzmy, książkę z 1000 stron, którą chcesz odwrócić, wykonanie jej potrwa bardzo długo.

Rozwiązaniem, które niektórzy mogą sugerować, jest użycie StringBuilder. Konstruktor ciągów znaków, który wykonuje + =, polega na tym, że przydziela dużo większe fragmenty pamięci, aby pomieścić nowy znak, dzięki czemu nie musi on dokonywać realokacji za każdym razem, gdy dodajesz znak.

Jeśli naprawdę chcesz szybkiego i minimalnego rozwiązania, sugeruję:

            char[] chars = new char[str.Length];
            for (int i = str.Length - 1, j = 0; i >= 0; --i, ++j)
            {
                chars[j] = str[i];
            }
            str = new String(chars);

W tym rozwiązaniu istnieje jeden początkowy przydział pamięci podczas inicjalizacji char [] i jeden przydział, gdy konstruktor ciągu buduje ciąg z tablicy char.

W moim systemie przeprowadziłem dla ciebie test, który odwraca ciąg 2 750 000 znaków. Oto wyniki dla 10 egzekucji:

StringBuilder: 190 tys. - 200 tys. Tyknięć

Tablica znaków: od 130 do 160 tyknięć

Przeprowadziłem również test normalnego ciągu + =, ale porzuciłem go po 10 minutach bez wyjścia.

Zauważyłem jednak również, że w przypadku mniejszych ciągów StringBuilder jest szybszy, więc będziesz musiał zdecydować o implementacji na podstawie danych wejściowych.

Twoje zdrowie

public static string reverse(string s) 
{
    string r = "";
    for (int i = s.Length; i > 0; i--) r += s[i - 1];
    return r;
}

public static string Reverse2(string x)
        {
            char[] charArray = new char[x.Length];
            int len = x.Length - 1;
            for (int i = 0; i <= len; i++)
                charArray[i] = x[len - i];
            return new string(charArray);
        }