c# - Le meilleur moyen d'inverser une chaîne





.net performance algorithm unicode (25)


Essayez d'utiliser Array.Reverse


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

J'ai juste dû écrire une fonction inverse de chaîne dans C # 2.0 (c'est-à-dire LINQ non disponible) et suis arrivé avec ceci:

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

Personnellement, je ne suis pas fou de la fonction et je suis convaincu qu'il y a une meilleure façon de le faire. Y a-t-il?




Ne vous embêtez pas avec une fonction, faites-le simplement en place. Remarque: La deuxième ligne lancera une exception d'argument dans la fenêtre Exécution de certaines versions de VS.

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



private static string Reverse(string str)
        {
            string revStr = string.Empty;
            for (int i = str.Length - 1; i >= 0; i--)
            {
                revStr += str[i].ToString();
            }
            return revStr;
        }

Faster than above method

private static string ReverseEx(string str)
        {
            char[] chrArray = str.ToCharArray();
            int len = chrArray.Length - 1;
            char rev = 'n';
            for (int i = 0; i <= len/2; i++)
            {
                rev = chrArray[i];
                chrArray[i] = chrArray[len - i];
                chrArray[len - i] = rev;
            }
            return new string(chrArray);
        }



How about use Substring

static string ReverseString(string text)
{
    string sub = "";
    int indexCount = text.Length - 1;
    for (int i = indexCount; i > -1; i--)
    {
        sub = sub + text.Substring(i, 1);
    }
    return sub;
}



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

Bien sûr, vous pouvez étendre la classe de chaînes avec la méthode Reverse

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



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



Que diriez-vous:

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



Tout d'abord, vous n'avez pas besoin d'appeler ToCharArray car une chaîne peut déjà être indexée en tant que tableau char, ce qui vous permettra d'économiser une allocation.

L'optimisation suivante consiste à utiliser un StringBuilder pour empêcher les allocations inutiles (comme les chaînes sont immuables, les concaténer fait une copie de la chaîne à chaque fois). Pour optimiser encore cela, nous avons prédéfini la longueur de StringBuilder afin qu'il StringBuilder pas besoin d'étendre sa mémoire tampon.

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

Edit: Données de performance

J'ai testé cette fonction et la fonction en utilisant Array.Reverse avec le programme simple suivant, où Reverse1 est une fonction et Reverse2 est l'autre:

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

Il s'avère que pour les cordes courtes, la méthode Array.Reverse est environ deux fois plus rapide que celle ci-dessus, et pour les cordes plus longues, la différence est encore plus prononcée. Donc, étant donné que la méthode Array.Reverse est à la fois plus simple et plus rapide, je vous recommande d'utiliser cela plutôt que celui-ci. Je laisse celle-ci ici juste pour montrer que ce n'est pas comme ça que tu devrais le faire (à ma grande surprise!)




Si la chaîne contient des données Unicode (à proprement parler, des caractères non-BMP) les autres méthodes qui ont été postées le corrompre, car vous ne pouvez pas permuter l'ordre des unités de code de substitution haute et basse lors de l'inversion de la chaîne. (Plus d'informations à ce sujet peuvent être trouvées sur mon blog .)

L'exemple de code suivant inversera correctement une chaîne qui contient des caractères non-BMP, par exemple, "\ U00010380 \ U00010381" (Lettre alphabétique Alpa, bêta-lettre Ugaritic).

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



As simple as this:

string x = "your string";       
string x1 = "";
for(int i = x.Length-1 ; i >= 0; i--)
    x1 += x[i];
Console.WriteLine("The reverse of the string is:\n {0}", x1);

See the output .




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



Cela s'avère être une question étonnamment difficile.

Je recommande d'utiliser Array.Reverse pour la plupart des cas car il est codé nativement et il est très simple à maintenir et à comprendre.

Il semble surpasser StringBuilder dans tous les cas que j'ai testés.

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

Il y a une seconde approche qui peut être plus rapide pour certaines longueurs de corde qui utilise 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);
    }

Remarque Si vous souhaitez prendre en charge le jeu de caractères Unicode UTF16 complet, lisez ceci . Et utilisez l'implémentation à la place. Il peut être encore optimisé en utilisant l'un des algorithmes ci-dessus et en parcourant la chaîne pour le nettoyer après l'inversion des caractères.

Voici une comparaison des performances entre les méthodes StringBuilder, Array.Reverse et 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();
        }
    }
}

Voici les résultats:

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.

Il semble que Xor peut être plus rapide pour les chaînes courtes.




If you have a string that only contains ASCII characters, you can use this method.

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



Jetez un oeil à l'entrée wikipedia here . Ils implémentent la méthode d'extension String.Reverse. Cela vous permet d'écrire du code comme ceci:

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

Ils utilisent également la combinaison ToCharArray / Reverse que d'autres réponses à cette question suggèrent. Le code source ressemble à ceci:

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



"Better way" depends on what is more important to you in your situation, performance, elegance, maintainability etc.

Anyway, here's an approach using 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);



Doit soumettre un exemple récursif:

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



Si vous voulez jouer à un jeu vraiment dangereux, c'est de loin le moyen le plus rapide (environ quatre fois plus rapide que la méthode Array.Reverse ). C'est un reverse sur place en utilisant des pointeurs.

Notez que je ne recommande vraiment pas cela pour n'importe quelle utilisation, ( regardez ici pour quelques raisons pourquoi vous ne devriez pas utiliser cette méthode ), mais c'est juste intéressant de voir que cela peut être fait, et que les chaînes ne sont pas vraiment immuables Une fois que vous avez activé le code dangereux.

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 a affiché une option unsafe qui est en effet aussi rapide que possible (c'est une inversion sur place); mais, comme il l'a indiqué dans sa réponse, c'est une idée complètement désastreuse .

Cela dit, je suis surpris qu'il y ait tellement de consensus que Array.Reverse est la méthode la plus rapide. Il y a toujours une approche unsafe qui renvoie une copie inversée d'une chaîne (pas de Array.Reverse ) significativement plus rapide que la méthode Array.Reverse pour les petites chaînes:

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

Voici quelques résultats de référence .

Vous pouvez voir que le gain de performance diminue puis disparaît par rapport à la méthode Array.Reverse lorsque les chaînes deviennent plus grandes. Pour les cordes de petite et moyenne taille, cependant, il est difficile de battre cette méthode.




La réponse facile et agréable utilise la méthode d'extension:

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

et voici la sortie:

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



Désolé pour un long post, mais cela pourrait être intéressant

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

Résultats:

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



De plus de 3.5 Cadre

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



If it ever came up in an interview and you were told you can't use Array.Reverse, i think this might be one of the fastest. It does not create new strings and iterates only over half of the array (ie O(n/2) iterations)

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



Sorry for posting on this old thread. I am practicing some code for an interview.

This was what I came up with for C#. My first version before refactoring was horrible.

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

In Contrast to the Array.Reverse method below, it appears faster with 12 characters or less in the string. After 13 characters, the Array.Reverse starts to get faster, and it eventually dominates pretty heavily on speed. I just wanted to point out approximately where the speed starts to change.

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

    Array.Reverse(charA);

    return new String(charA);
}

At 100 characters in the string, it is faster than my version x 4. However, if I knew that the strings would always be less than 13 characters, I would use the one I made.

Testing was done with Stopwatch and 5000000 iterations. Also, I'm not sure if my version handles Surrogates or combined character situations with Unicode encoding.




Si vous souhaitez utiliser map pour effectuer cette opération sur plusieurs chaînes dans une liste, vous devrez utiliser str.lower et pas simplement:

words = ['CATS', 'KITTENS', 'Pirate Cats', 'fluffy felines']
list(map(str.lower, words))

Résultats

['cats', 'kittens', 'pirate cats', 'fluffy felines']






c# .net performance algorithm unicode