Meilleure façon d’inverser une chaîne

Question

J’ai juste eu à écrire une fonction inverse de la chaîne en c# 2.0 (c.-à-d. LINQ n’est pas disponible) et venu à ceci :

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

Answer 1

<pre><code></code><p>Je pense que les ouvrages ci-dessus, ne pas testés, bien que la classe stringbuilder peut également avoir une fonction inverse, je n’ai pas vérifié que si.</p></pre>

Answer 2

Voici une solution qui renverse la chaîne "Les Mise\u0301rables" comme "selbare\u0301siM seL". Cela devrait rendre juste comme selbarésiM seL, pas selbaŕesiM seL (noter la position de l'accent), comme ce serait 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 (la marche 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 en direct l'exécution de l'exemple ici: https://ideone.com/DqAeMJ)

Il utilise simplement la .NET API pour graphème cluster itération, qui a été là depuis toujours, mais un peu "cachée" de vue, il me semble.

Answer 3

Ce se révèle être étonnamment délicate question.

Je vous conseille d'utiliser un Tableau.Inverse pour la plupart des cas, que c'est codé en mode natif et il est très simple à maintenir et à comprendre.

Il semble surpasser StringBuilder dans tous les cas je l'ai testé.

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 deuxième approche qui peut être plus rapide pour certaines longueurs de chaîne 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 soutenir l'Unicode complet UTF16 charset lire ce. Et l'utilisation de la mise en œuvre il ya lieu. Il peut être optimisée en utilisant un des algorithmes ci-dessus et en cours d'exécution à travers la chaîne de la nettoyer après les caractères sont inversés.

Voici une comparaison des performances entre le StringBuilder, Tableau.Inverse et Xor méthode.

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 chaînes courtes.

Answer 4

Salut, nous pouvons utiliser comme ça aussi au-dessus de Framework 3.5

Answer 5

Si la chaîne contient des données Unicode (à strictement parler, non BMP caractères) les autres méthodes qui ont été la publication de la corrompre, parce que vous ne pouvez pas permuter l'ordre de la haute et basse de substitution des unités de code 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 correctement inverser une chaîne de caractères qui contient non BMP caractères, par exemple, "\U00010380\U00010381" (Ougaritiques Lettre de l'Alpa, Ougaritiques Lettre Bêta).

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