Beste Methode zur Umkehrung einer Zeichenkette

Question

Ich habe gerade eine String-Reverse-Funktion in C# 2.0 (d.h. LINQ nicht verfügbar) schreiben musste und kam mit diesem:

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

Ich persönlich bin von dieser Funktion nicht begeistert und bin überzeugt, dass es eine bessere Lösung gibt. Gibt es eine?

Answer 1

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

Answer 2

Hier eine Lösung, die die Zeichenfolge richtig umkehrt "Les Mise\u0301rables" como "selbare\u0301siM seL" . Dies sollte genau wie selbarésiM seL ではなく selbaresiM seL (man beachte die Position des Akzents), wie es auch das Ergebnis der meisten Implementierungen auf der Grundlage von Codeeinheiten ( Array.Reverse usw.) oder sogar Code-Punkte (mit besonderer Sorgfalt bei Surrogatpaaren umkehren).

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

(Und hier ein Live-Beispiel: https://ideone.com/DqAeMJ )

Es verwendet einfach die .NET API für Graphem-Cluster-Iteration die schon immer da war, aber etwas "versteckt", wie es scheint.

Answer 3

Diese Frage erweist sich als überraschend schwierig.

Ich würde empfehlen, Array.Reverse für die meisten Fälle zu verwenden, da es nativ kodiert ist und es sehr einfach zu pflegen und zu verstehen ist.

Es scheint in allen von mir getesteten Fällen besser zu sein als StringBuilder.

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

Es gibt einen zweiten Ansatz, der bei bestimmten Zeichenfolgenlängen schneller sein kann. verwendet 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);
    }

Hinweis Wenn Sie den vollständigen Unicode-Zeichensatz UTF16 unterstützen möchten dies lesen . Und verwenden Sie stattdessen die dortige Implementierung. Sie kann weiter optimiert werden, indem man einen der oben genannten Algorithmen verwendet und die Zeichenfolge durchläuft, um sie zu bereinigen, nachdem die Zeichen umgekehrt wurden.

Hier ein Leistungsvergleich zwischen dem StringBuilder, Array.Reverse und der Xor-Methode.

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

Hier sind die Ergebnisse:

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.

Es scheint, dass Xor bei kurzen Zeichenketten schneller sein kann.

Answer 4

Wenn Sie LINQ (.NET Framework 3.5+) verwenden können, erhalten Sie mit dem folgenden Einzeiler einen kurzen Code. Vergessen Sie nicht, hinzuzufügen using System.Linq; Zugang zu haben zu Enumerable.Reverse :

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

Anmerkungen:

• nicht die schnellste Version - laut Martin Niederl 5,7 Mal langsamer als die schnellste Wahl hier.
• Dieser Code wie auch viele andere Optionen ignoriert alle Arten von Kombinationen aus mehreren Zeichen, so dass die Verwendung auf Hausaufgaben und Zeichenfolgen beschränkt ist, die nicht solche Zeichen enthalten. Siehe eine andere Antwort in dieser Frage für eine Implementierung, die solche Kombinationen korrekt behandelt.

Answer 5

Wenn die Zeichenkette Unicode-Daten enthält (genau genommen Nicht-BMP-Zeichen), wird sie durch die anderen beschriebenen Methoden beschädigt, da Sie die Reihenfolge der hohen und niedrigen Surrogat-Codeeinheiten beim Umkehren der Zeichenkette nicht vertauschen können. (Weitere Informationen hierzu finden Sie unter mein Blog .)

Das folgende Codebeispiel kehrt eine Zeichenkette, die Nicht-BMP-Zeichen enthält, korrekt um, z. B. " \U00010380\U00010381 "(Ugaritischer Buchstabe Alpa, Ugaritischer Buchstabe 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);
}