Лучший способ перевернуть строку

Question

Мне просто нужно было написать функцию обратного преобразования строк в C # 2.0 (т. Е. LINQ недоступен) и придумал следующее:

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

Лично я не в восторге от этой функции и убежден, что есть лучший способ сделать это. Есть ли?

Answer 1

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

Answer 2

Здесь решение, которое правильно меняет строку "Les Mise\u0301rables" как "selbare\u0301siM seL". Это должно отображаться так же, как selbarésiM seL, а не selbaŕesiM seL (обратите внимание на положение акцента), как это было бы в результате большинства реализаций, основанных на единицах кода (Array.Reverse и т. Д.) Или даже на кодовых точках (обращаясь с особым вниманием к суррогатные пары).

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

(И пример работающего вживую здесь: https://ideone.com/DqAeMJ)

Он просто использует API .NET для итерации кластера графем , который был там с тех пор, но кажется немного «скрытым» от глаз.

Answer 3

Это оказывается удивительно сложным вопросом.

Я бы порекомендовал использовать Array.Reverse для большинства случаев, поскольку он изначально закодирован и его очень просто поддерживать и понимать.

Кажется, он превосходит StringBuilder во всех случаях, которые я тестировал.

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

Существует второй подход, который может быть быстрее для определенных длин строк, который использует 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);
    }

Примечание Если вы хотите поддерживать полную кодировку Unicode UTF16 , прочитайте это . И используйте реализацию там вместо этого. Его можно дополнительно оптимизировать, используя один из приведенных выше алгоритмов и пропуская строку, чтобы очистить ее после обращения символов.

Вот сравнение производительности между методами StringBuilder, Array.Reverse и 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();
        }
    }
}

Вот результаты:

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.

Кажется, что Xor может быть быстрее для коротких строк.

Answer 4

Если строка содержит данные Unicode (строго говоря, не-BMP-символы), другие опубликованные методы повредят ее, потому что вы не можете поменять местами порядковые единицы высокого и низкого суррогатного кода при обращении строки. (Более подробную информацию об этом можно найти в моем блоге .)

Следующий пример кода правильно перевернет строку, содержащую символы, отличные от BMP, например, "\ U00010380 \ U00010381" (Ugaritic Letter Alpa, Ugaritic Letter 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);
}

Answer 5

Сверху 3,5 рамки

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

Answer 6

Хорошо, в интересах «не повторяйся» я предлагаю следующее решение:

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

Насколько я понимаю, эта реализация, доступная по умолчанию в VB.NET, правильно обрабатывает символы Юникода.

Answer 7

Грег Бич опубликовал опцию unsafe, которая действительно настолько быстра, насколько это возможно (это разворот на месте); но, как он указал в своем ответе, это совершенно катастрофическая идея .

Тем не менее, я удивлен, что консенсуса так много, что Array.Reverse - самый быстрый метод. Все еще существует подход unsafe, который возвращает обратную строку (без изменений на месте) значительно быстрее, чем Array.Reverse метод для небольших строк:

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

Вот некоторые результаты тестов .

Вы можете видеть, что прирост производительности уменьшается, а затем исчезает по сравнению с методом Array.Reverse, когда строки становятся больше. Однако для струн малого и среднего размера этот метод сложно обойти.

Answer 8

Простой и приятный ответ - использование метода расширения:

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

и вот вывод:

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

Answer 9

Если вы хотите играть в действительно опасную игру, то это самый быстрый способ (примерно в четыре раза быстрее, чем метод Array.Reverse). Это реверс на месте с использованием указателей.

Обратите внимание, что я действительно не рекомендую это для любого использования, когда-либо ( посмотрите здесь по некоторым причинам, почему вы не должны использовать этот метод ), но просто интересно посмотреть, что это можно сделать и эти строки не могут быть неизменными после включения небезопасного кода.

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

Answer 10

Во-первых, вам не нужно вызывать ToCharArray, поскольку строку уже можно проиндексировать как массив символов, так что это сэкономит вам выделение.

Следующая оптимизация заключается в использовании StringBuilder для предотвращения ненужных выделений (поскольку строки неизменяемы, их объединение делает копию строки каждый раз). Для дальнейшей оптимизации мы предварительно установили длину StringBuilder, чтобы не нужно было расширять ее буфер.

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

Редактировать: данные о производительности

Я протестировал эту функцию и функцию, используя Array.Reverse с помощью следующей простой программы, где Reverse1 - это одна функция, а Reverse2 - другая:

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

Оказывается, что для коротких строк метод Array.Reverse примерно в два раза быстрее, чем приведенный выше, а для более длинных строк разница еще более выражена. Поэтому, учитывая, что метод Array.Reverse проще и быстрее, я бы порекомендовал вам использовать его, а не этот. Я оставляю это здесь, чтобы показать, что вы не должны делать это (к моему большому удивлению!)