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

Ok, im Interesse von "wiederhole dich nicht" biete ich die folgende Lösung an:

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

Meines Erachtens ist diese Implementierung, die standardmäßig in VB.NET verfügbar ist, in der Lage, Unicode-Zeichen korrekt zu verarbeiten.

Answer 2

Ab .NET Core 2.1 gibt es eine neue Möglichkeit, eine Zeichenkette umzukehren, indem man die string.Create Methode.

Beachten Sie, dass diese Lösung Unicode-Kombinationszeichen usw. nicht korrekt behandelt, da "Les Mise \u0301rables " würde in "selbarésiM seL" umgewandelt werden. Siehe die anderen Antworten für eine bessere Lösung.

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

Dies kopiert im Wesentlichen die Zeichen von input in eine neue Zeichenfolge um und kehrt die neue Zeichenfolge an Ort und Stelle um.

Warum ist string.Create nützlich?

Wenn wir eine Zeichenkette aus einem bestehenden Array erstellen, wird ein neues internes Array zugewiesen und die Werte werden kopiert. Andernfalls wäre es möglich, eine Zeichenkette nach ihrer Erstellung (in einer sicheren Umgebung) zu verändern. Das heißt, im folgenden Ausschnitt müssen wir ein Array der Länge 10 zweimal zuweisen, einmal als Puffer und einmal als internes Array der Zeichenkette.

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

string.Create ermöglicht es uns im Wesentlichen, das interne Array während der Erstellung der Zeichenkette zu manipulieren. Das heißt, wir brauchen keinen Puffer mehr und können daher die Zuweisung des einen Char-Arrays vermeiden.

Steve Gordon hat darüber ausführlicher geschrieben aquí . Es gibt auch einen Artikel über MSDN .

Wie zu verwenden string.Create ?

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

Die Methode benötigt drei Parameter:

1. Die Länge der zu erstellenden Zeichenkette,
2. die Daten, die zur dynamischen Erstellung der neuen Zeichenfolge verwendet werden sollen,
3. und einen Delegaten, der die endgültige Zeichenkette aus den Daten erstellt, wobei der erste Parameter auf die interne char Array der neuen Zeichenkette und das zweite sind die Daten (Status), die Sie an string.Create .

Innerhalb des Delegaten können wir angeben, wie die neue Zeichenkette aus den Daten erstellt wird. In unserem Fall kopieren wir einfach die Zeichen der Eingabezeichenfolge in den Span von der neuen Zeichenfolge verwendet. Dann kehren wir die Span und somit wird die gesamte Zeichenkette umgedreht.

Benchmarks

Um die von mir vorgeschlagene Methode zur Umkehrung einer Zeichenkette mit der akzeptierten Antwort zu vergleichen, habe ich zwei Benchmarks mit BenchmarkDotNet geschrieben.

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

Hier sind die Ergebnisse auf meinem Rechner:

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

Wie Sie sehen können, mit ReverseWithStringCreate wird nur die Hälfte des Speichers zugewiesen, der von der ReverseWithArray Methode.

Answer 3

Schauen Sie sich den Wikipedia-Eintrag an aquí . Sie implementieren die Erweiterungsmethode String.Reverse. Dies ermöglicht es Ihnen, Code wie diesen zu schreiben:

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

Sie verwenden auch die Kombination ToCharArray/Reverse, die in anderen Antworten auf diese Frage vorgeschlagen wird. Der Quellcode sieht wie folgt aus:

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

Answer 4

Greg Beech hat eine unsafe Option, die in der Tat so schnell ist, wie es nur geht (es handelt sich um eine Umkehrung an Ort und Stelle); aber, wie er in seiner Antwort andeutete, ist es eine völlig verhängnisvolle Idee .

Dennoch bin ich überrascht, dass so viel Einigkeit darüber besteht, dass Array.Reverse ist die schnellste Methode. Es gibt noch eine unsafe Ansatz, der eine umgekehrte Kopie einer Zeichenkette zurückgibt (keine Umkehrung an Ort und Stelle) deutlich schneller als die Array.Reverse Methode für kleine Saiten:

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

Hier sind einige Benchmark-Ergebnisse .

Sie können sehen, dass der Leistungsgewinn schrumpft und dann verschwindet gegen die Array.Reverse Methode, wenn die Zeichenketten größer werden. Für kleine bis mittelgroße Saiten ist diese Methode jedoch kaum zu schlagen.

Answer 5

Die einfache und schöne Antwort ist die Verwendung der Erweiterungsmethode:

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

und hier ist die Ausgabe:

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