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

440

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?

Chłopak
źródło
51
Zaskakująco trudne, jeśli chcesz odpowiedniego wsparcia międzynarodowego. Przykład: chorwacki / serbski ma dwuznakowe litery lj, nj itp. Właściwym odwrotnością „ljudi” jest „idulj”, NIE „idujl”. Jestem pewien, że
wypadłbyś
Zastanawiam się, czy wolniej jest konkatować ciąg zamiast inicjować tablicę tymczasową i przechowywać w niej wyniki, a następnie przekształcić ją w ciąg?
The Muffin Man
2
Znacznie nowszy powiązany wątek: Odwrócić ciąg znaków z znakami akcentującymi?
Jeppe Stig Nielsen
5
To pytanie można poprawić, definiując, co rozumiesz przez „najlepszy”. Najszybszy? Najbardziej czytelny? Najbardziej niezawodny w różnych przypadkach skrajnych (kontrole zerowe, wiele języków itp.)? Najbardziej konserwowalny w różnych wersjach C # i .NET?
hypehuman

Odpowiedzi:

608
public static string Reverse( string s )
{
    char[] charArray = s.ToCharArray();
    Array.Reverse( charArray );
    return new string( charArray );
}
PeteT
źródło
16
sambo99: Nie trzeba wspominać o Unicode: znaki w C # to znaki Unicode, a nie bajty. Xor może być szybszy, ale poza tym, że jest znacznie mniej czytelny, może to być nawet to, czego Array.Reverse () używa wewnętrznie.
Nick Johnson
27
@Arachnid: W rzeczywistości znaki w C # są jednostkami kodu UTF-16; dwa z nich reprezentują charakter uzupełniający. Zobacz jaggersoft.com/csharp_standard/9.4.1.htm .
Bradley Grainger
4
Tak, sambo99 Chyba masz rację, ale używanie UTF-32 jest dość rzadkim przypadkiem. A XOR jest szybszy tylko dla bardzo małego zakresu wartości, poprawną odpowiedzią byłoby, jak sądzę, wdrożenie różnych metod dla różnych długości. Jest to jednak jasne i zwięzłe, co moim zdaniem jest zaletą.
PeteT,
21
Znaki kontrolne Unicode sprawiają, że ta metoda jest bezużyteczna w przypadku zestawów znaków innych niż łacińskie. Zobacz wyjaśnienie Jona Skeeta, używając marionetki do skarpet: codeblog.jonskeet.uk/2009/11/02/… (1/4 w dół), lub wideo: vimeo.com/7516539
Callum Rogers
20
Mam nadzieję, że nie spotkasz żadnych surogatów ani łączenia postaci.
dalle
183

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

R. Martinho Fernandes
źródło
10
+1 Jedna z niewielu poprawnych odpowiedzi, o wiele bardziej elegancka i przyszłościowa niż jakakolwiek inna, IMO
patrz
Nie udaje się to jednak w przypadku niektórych rzeczy zależnych od ustawień regionalnych.
R. Martinho Fernandes
7
To zabawne, jak większość innych osób odpowiadających na pytania próbuje pozbyć się ms z niewłaściwych podejść. Jak reprezentatywny.
G. Stoynev,
2
Właściwie jest znacznie szybsze tworzenie instancji StringInfo (s), a następnie iterowanie przez SubstringByTextElements (x, 1) i budowanie nowego ciągu za pomocą StringBuilder.
2
To trochę dziwne, że użyłeś przykładu Jona Skeeta, który podał wiele lat wcześniej codeblog.jonskeet.uk/2009/11/02/... Les Misérables (chociaż Jon nie wspomniał o rozwiązaniu, tylko wymienił problemy). Dobrze, że wpadłeś na rozwiązanie. Być może Jon Skeet wynalazł wehikuł czasu, wrócił do 2009 roku i podał przykład problemu, którego użyłeś w swoim rozwiązaniu.
barlop
126

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.

Sam Saffron
źródło
2
To nie zwraca ciągu - musisz zawinąć to w wywołanie „new String (...)”
Greg Beech
BTW .. Właśnie obejrzałem implementację Array.Reverse i zrobiłem to naiwnie dla znaków ... powinno być znacznie szybsze niż opcja StringBuilder.
Sam Saffron
Jak miło z twojej strony, Greg, że powstrzymujesz Sambo przed znalezieniem lepszego rozwiązania zamiast głosować w dół.
DOK
@ dok1 - nie wspominaj o tym :) @ sambo99 - teraz jestem zaintrygowany, jutro będę musiał wyciągnąć profilera kodu i rzucić okiem!
Greg Beech
9
Te metody nie obsługują ciągów zawierających znaki spoza Podstawowej płaszczyzny wielojęzycznej, tj. Znaki Unicode> = U + 10000, które są reprezentowane przez dwa znaki C #. Wysłałem odpowiedź, która poprawnie obsługuje takie ciągi.
Bradley Grainger
52

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.
SGRao
źródło
To około 5,7 razy wolniej niż najbardziej popularna wersja, więc nie polecam jej używać!
Martin Niederl
2
Nie jest to najszybsze rozwiązanie, ale przydatne jako jedna linijka.
adrianmp
49

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);
}
Bradley Grainger
źródło
29
W rzeczywistości znaki w C # to 16-bitowe jednostki kodu UTF-16; dodatkowa postać jest kodowana przy użyciu dwóch z nich, więc jest to konieczne,
Bradley Grainger
14
Wygląda na to, że System.String naprawdę powinien ujawnić właściwość HereBeDragons dla ciągów znaków, które zawierają dodatkowe znaki Unicode.
Robert Rossney
4
@SebastianNegraszus: Zgadza się: ta metoda po prostu odwraca punkty kodowe w ciągu. Odwrócenie klastrów grafemu byłoby prawdopodobnie bardziej „przydatne” ogólnie (ale jaki jest „użytek” odwrócenia dowolnego ciągu?), Ale nie jest łatwe do wdrożenia za pomocą tylko wbudowanych metod w .NET Framework.
Bradley Grainger
2
@Richard: Reguły dotyczące łamania klastrów grafemowych są nieco bardziej skomplikowane niż wykrywanie łączenia punktów kodowych; więcej informacji można znaleźć w dokumentacji dotyczącej granic klastra Grapheme w UAX # 29.
Bradley Grainger
1
Bardzo dobra informacja! Czy KTOŚ ma uszkodzoną test test Array.reverse? I przez test mam na myśli przykładowy ciąg, a nie cały test jednostkowy ... To naprawdę pomogłoby mi (i innym) przekonać różne osoby o tym problemie.
Andrei Rînea
25

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.

richardtallent
źródło
11
To tylko odpowiednio obsługuje surogaty. Wmiesza się łączenie znaków: ideone.com/yikdqX .
R. Martinho Fernandes,
17

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

Dan Tao
źródło
2
StackOverflow na dużych ciągach.
Raz Megrelidze
@rezomegreldize: Tak, to się stanie;)
Dan Tao
15

Ł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"
Mehdi Khademloo
źródło
Reverse()i ToArray()są w niewłaściwej kolejności w przykładowym kodzie.
Chris Walsh
W jakim celu służy @?
user5389726598465,
2
@ user5389726598465 Zobacz ten link: docs.microsoft.com/en-us/dotnet/csharp/language-reference/… Ponieważ „base” jest słowem kluczowym w języku C #, musi być poprzedzony znakiem @, aby kompilator C # zinterpretował go jako identyfikator.
Dyndrilliac
14

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;
    }
}
Greg Beech
źródło
Jestem prawie pewien, że to zwróci niepoprawne wyniki dla ciągów utf16, to naprawdę sprawia problemy :)
Sam Saffron
Cześć, powinieneś link do tego postu na tym stackoverflow.com/questions/229346/… , jak powiedziałem wcześniej, to naprawdę prosi o kłopoty ...
Sam Saffron
Może to być całkowicie złe i niezrozumiałe (jak sam przyznasz), ale wciąż istnieje wysoce wydajny sposób na odwrócenie łańcucha przy użyciu unsafekodu, który nie jest zły i wciąż bije Array.Reverse. Spójrz na moją odpowiedź.
Dan Tao
13

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);
}
Mike Thompson
źródło
To wspaniale, tyle że metody rozszerzenia nie zostały wprowadzone w c # 2.0.
Kobi
11

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

Greg Beech
źródło
Czy przechowywanie tekstu. Długość w zmiennej nie dałoby nieco większej prędkości, gdy odwołujesz się do niego przez obiekt?
David Robbins,
10

Spróbuj użyć Array.Reverse


public string Reverse(string str)
{
    char[] array = str.ToCharArray();
    Array.Reverse(array);
    return new string(array);
}
Mike Two
źródło
To jest niesamowicie szybkie.
Michael Stum
Dlaczego głosowanie w dół? Nie spieram się, ale wolę uczyć się na własnych błędach.
Mike Two
Nie radzi sobie z łączeniem punktów kodu między wieloma innymi rzeczami.
Mooing Duck
@MooingDuck - dziękuję za wyjaśnienie, ale nie wiem, co masz na myśli przez punkty kodowe. Czy mógłbyś także rozwinąć „wiele innych rzeczy”.
Mike Two
@MooingDuck Sprawdziłem punkty kodowe. Tak. Masz rację. Nie obsługuje punktów kodowych. Trudno jest określić wszystkie wymagania dotyczące tak prostego pytania. Dzięki za opinie
Mike Two
10
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));
    }
}
Vlad Bezden
źródło
Enumerable.Reverse(input)jest równyinput.Reverse()
fubo
8

„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̽"  👍
Slai
źródło
8

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

Flogex
źródło
Jest znacznie szybszy niż rewers Linq
code4j
7

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()); 
BH
źródło
1
Jakiś facet poświęcił czas na zanegowanie każdej odpowiedzi (w tym mojej) bez wyjaśnienia dlaczego.
Marcel Valdez Orozco
To nie jest tak naprawdę na miejscu, ponieważ tworzysznew string
mbadawi23
5

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
aku
źródło
Dodałem podobne porównanie w moim poście, jest to wiki społeczności, więc powinieneś być w stanie edytować. Wydajność naprawdę zależy od długości łańcucha, a także od algorytmu, warto go przedstawić na wykresie. Nadal uważam, że Array.Reverse będzie najszybszy we wszystkich przypadkach ...
Sam Saffron,
„będzie najszybszy we wszystkich przypadkach”, gdy zawiedzie magiczna funkcja TrySZReverse (jest używana w implementacji Reverse), Array.Reverse wraca do prostej implementacji obejmującej boks, więc moja metoda wygra. Nie wiem jednak, co jest warunkiem niepowodzenia TrySZReverse.
ak
Okazuje się, że nie jest najszybszy we wszystkich przypadkach :), zaktualizowałem swój post. Nadal należy to przetestować za pomocą Unicode zarówno pod względem poprawności, jak i szybkości.
Sam Saffron
5
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
Marcel Valdez Orozco
źródło
1
Musisz sprawdzić pusty ciąg znaków w Reverse(...). W przeciwnym razie dobra robota.
Lara,
5

Najprostszy sposób:

string reversed = new string(text.Reverse().ToArray());
Shady Sirhan
źródło
Używam tego samego zdania
VhsPiceros
4

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);
    }
Raz Megrelidze
źródło
4

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));
}
JPrescottSanders
źródło
1
ciąg długości 0 nie jest obsługiwany
bohdan_trotsenko
To nie jest przydatne.
user3613932,
3

Co powiesz na:

    private string Reverse(string stringToReverse)
    {
        char[] rev = stringToReverse.Reverse().ToArray();
        return new string(rev); 
    }
Zamir
źródło
Ma takie same problemy ze współrzędnymi kodowymi jak inne metody powyżej i będzie działał znacznie wolniej niż przy ToCharArraypierwszym. Moduł wyliczający LINQ jest również znacznie wolniejszy niż Array.Reverse().
Abel
3

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();
}
natenho
źródło
+1, miły dodatek! Właśnie próbowałem go string s = "abo\u0327\u0307\u035d\U0001d166cd", który zawiera literę, oa następnie 3 łączące znaki diakrytyczne w BMP i jeden znak łączący (MEMICAL SYMBOL COMBINING STEM) z płaszczyzny astralnej (bez BMP) i utrzymuje je w stanie nienaruszonym. Ale metoda jest powolna, jeśli takie znaki pojawiają się tylko na końcu długiego łańcucha, ponieważ musi przejść dwa razy w całej tablicy.
Abel
3

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.

Jason Ausborn
źródło
2

„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);
Popiół
źródło
2

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);
    }
mike01010
źródło
2
Jestem całkiem pewien, że wywołanie stringToReverse.ToCharArray () wygeneruje czas wykonania O (N).
Marcel Valdez Orozco
W notacji Big-O współczynnik nie zależny xlub w twoim przypadku nnie jest używany. Twój algorytm ma wydajność f(x) = x + ½x + C, gdzie C jest trochę stałe. Ponieważ oba Cte czynniki nie są zależne x, algorytm jest O(x). Nie oznacza to, że nie będzie szybszy dla żadnego wejścia długości x, ale jego wydajność jest liniowo zależna od długości wejścia. Aby odpowiedzieć na @MarcelValdezOrozco, tak, tak jest O(n), chociaż kopiuje się na 16-bajtowe porcje w celu zwiększenia prędkości (nie używa prostej memcpyna całej długości).
Abel
2

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);
    }
Raz Megrelidze
źródło
2

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

Reasurria
źródło
nie działa dla😀Les Misérables
Charles
@Charles Ah tak, istnieje ograniczenie char, które przypuszczam.
Reasurria,
2
public static string reverse(string s) 
{
    string r = "";
    for (int i = s.Length; i > 0; i--) r += s[i - 1];
    return r;
}
ddagsan
źródło
1
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);
        }
Shrini
źródło