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



Answers

Voici une solution qui inverse correctement la chaîne "Les Mise\u0301rables" comme "selbare\u0301siM seL" . (Cela devrait être le résultat de la plupart des implémentations basées sur des unités de code ( Array.Reverse , etc) ou même des points de code (inverser avec un soin particulier pour les paires de substitution). ).

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

(Et l'exemple de course en direct ici: https://ideone.com/DqAeMJ )

Il utilise simplement l' API .NET pour l'itération de grappe de graphèmes , qui existe depuis toujours, mais qui semble un peu "cachée" à la vue.

Question

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?




Que diriez-vous:

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



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



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



First of all what you have to understand is that str+= will resize your string memory to make space for 1 extra char. This is fine, but if you have, say, a book with 1000 pages that you want to reverse, this will take very long to execute.

The solution that some people might suggest is using StringBuilder. What string builder does when you perform a += is that it allocates much larger chunks of memory to hold the new character so that it does not need to do a reallocation every time you add a char.

If you really want a fast and minimal solution I'd suggest the following:

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

In this solution there is one initial memory allocation when the char[] is initialized and one allocation when the string constructor builds the string from the char array.

On my system I ran a test for you that reverses a string of 2 750 000 characters. Here are the results for 10 executions:

StringBuilder: 190K - 200K ticks

Char Array: 130K - 160K ticks

I also ran a test for normal String += but I abandoned it after 10 minutes with no output.

However, I also noticed that for smaller strings the StringBuilder is faster, so you will have to decide on the implementation based on the input.

À votre santé




J'ai créé un port C # à partir de Microsoft.VisualBasic.Strings . Je ne suis pas sûr pourquoi ils gardent de telles fonctions utiles (de VB) en dehors du System.String dans le cadre, mais toujours sous Microsoft.VisualBasic. Même scénario pour les fonctions financières (par exemple 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();
}



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



Essayez d'utiliser Array.Reverse


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



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



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



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"



Ok, dans l'intérêt de "ne vous répétez pas", j'offre la solution suivante:

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

Ma compréhension est que cette implémentation, disponible par défaut dans VB.NET, gère correctement les caractères Unicode.




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



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




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





Related