Array.Reverse алгоритм?

Question

Какой алгоритм Array.Reverse (строка a) использует за сценой для обращения строки?

Answer 1

ОБНОВЛЕНИЕ : в нижней части этого ответа приведен один действительно ужасающий результат изменения строки на месте в .NET.

---

«Хороший» ответ

В .NET нет перегрузки Array.Reverse, которая принимает string. Тем не менее, вот как можно реализовать, если бы он существовал:

static string ReverseString(string str) {
    char[] reversed = new char[str.Length];
    for (int i = 0; i < reversed.Length; ++i)
        reversed[i] = str[str.Length - 1 - i];
    return new string(reversed);
}

Обратите внимание, что в .NET этот метод должен возвращать a string, поскольку тип System.String является неизменным, и поэтому вы не можете повернуть один на месте.

---

Страшный ответ

OK, на самом деле, - это , позволяющий перевернуть строку на месте в .NET .

Вот один способ, который требует компиляции в режиме unsafe:

static unsafe void ReverseString(string str) {
    int i = 0;
    int j = str.Length - 1;

    fixed (char* fstr = str) {
        while (i < j) {
            char temp = fstr[j];

            fstr[j--] = fstr[i];
            fstr[i++] = temp;
        }
    }
}

А вот еще один способ, который использует отражение и не должен быть скомпилирован в режиме unsafe:

static void ReverseString(string str) {
    int i = 0;
    int j = str.Length - 1;

    // what a tricky bastard!
    MethodInfo setter = typeof(string).GetMethod(
        "SetChar",
        BindingFlags.Instance | BindingFlags.NonPublic
    );

    while (i < j) {
        char temp = str[j];

        setter.Invoke(str, new object[] { j--, str[i] });
        setter.Invoke(str, new object[] { i++, temp });
    }
}

Совершенно нецелесообразно и безрассудно, да - не говоря уже о том, что он, скорее всего, будет иметь ужасных производительность. Но, тем не менее, возможно.

---

Ужас

О, и, кстати, на случай, если у вас возникнут какие-либо сомнения в том, что вы должны никогда не делать ничего подобного : знайте, что любой из ReverseString методов, которые я предоставил выше, будет фактически позволяет вам написать следующую совершенно странную программу:

ReverseString("Hello!");
Console.WriteLine("Hello!");

Приведенный выше код выведет, хотите верьте, хотите нет *:

!olleH

Так что, да, если вы не хотите, чтобы весь ад вырвался из вашего кода, не переворачивайте строку на месте. Хотя технически вы можете;)

_{* Вы можете попробовать это сами, если не верите мне.}

Answer 2

Вероятно, стандартный алгоритм реверсирования на месте.

function reverse-in-place(a[0..n])
 for i from 0 to floor(n/2)
     swap(a[i], a[n-i])

Источники

• Википедия / алгоритм на месте

Answer 3

Согласно Reflector, Array.Reverse(Array) (без изменения строки) сначала вызывает что-то с именем TrySZReverse, для которого я не могу найти реализацию.Я предполагаю, что это какой-то сильно оптимизированный нативный метод.

Если это не удается, он делает что-то вроде этого:

int num = index;
int num2 = (index + length) - 1;
while (num < num2)
{
    object obj2 = objArray[num];
    objArray[num] = objArray[num2];
    objArray[num2] = obj2;
    num++;
    num2--;
}

Итак, алгоритм на месте, где он меняет значениякаждый конец, затем движется внутрь, несколько раз.

Answer 4

В алгоритме, вероятно, используются два указателя i и j , которые начинаются с 0 и длина -1 соответственно. Затем символы в позиции i и j меняются местами (с помощью временной переменной), и i увеличивается, а j уменьшается на 1. Эти шаги повторяются до тех пор, пока оба указателя не достигнут друг друга ( i ≥ j ).

В псевдокоде:

i := 0;
j := a.length-1;
while (i < j) do
    tmp := a[i];
    a[i] := a[j];
    a[j] := tmp;
    i := i+1;
    j := j-1;
endwhile;

Answer 5

Вот ответ общего назначения, не зависящий от языка и вопрос: он копирует входную строку в выходную строку, читая с одного конца и записывая с другого.

Answer 6

Мое предложение:

    private string Reverse(string text)
    {
        char[] c = text.ToCharArray(0, text.Length);
        Array.Reverse(c);
        return new string(c);
    }