ReverseString, вопрос C # интервью

Question

У меня был вопрос на собеседование, который попросил меня написать «отзыв» о куске кода, который написал младший программист. Они намекнули, что может быть проблема, и сказали, что они будут интенсивно использоваться на больших струнах.

public string ReverseString(string sz)
{
    string result = string.Empty;
    for(int i = sz.Length-1; i>=0; i--)
    {
      result += sz[i]
    }
    return result;
}

Я не мог определить это. Я не видел никаких проблем вообще. Оглядываясь назад, я мог бы сказать, что пользователь должен изменить размер, но похоже, что C # не имеет изменения размера (я парень C ++).

Я закончил тем, что написал такие вещи, как использование итератора, если это возможно, [x] в контейнерах не может быть произвольного доступа, поэтому он может быть медленным. и разные вещи. Но я определенно сказал, что мне никогда не приходилось оптимизировать код на C #, поэтому моё мышление не подвело меня на собеседовании.

Я хотел знать, в чем проблема с этим кодом, вы, ребята, видите его?

-edit-

Я изменил это в вики, потому что может быть несколько правильных ответов. Также я очень рад, что прямо сказал, что мне никогда не приходилось оптимизировать программу на C #, и упомянул разные вещи. К сожалению. Я всегда думал, что у C # не было проблем с производительностью такого рода вещей. упс.

Answer 1

Самое главное? Это снизит производительность - нужно создать много строк (по одной на символ) Самый простой способ это что-то вроде:

public static string Reverse(string sz) // ideal for an extension method
{
    if (string.IsNullOrEmpty(sz) || sz.Length == 1) return sz;
    char[] chars = sz.ToCharArray();
    Array.Reverse(chars);
    return new string(chars);
}

Answer 2

Проблема заключается в том, что объединение строк обходится дорого, поскольку строки неизменны в C #. Приведенный пример создаст новую строку на один символ длиннее каждой итерации, что очень неэффективно. Чтобы избежать этого, вы должны использовать класс StringBuilder , например:

public string ReverseString(string sz)
{
    var builder = new StringBuilder(sz.Length);
    for(int i = sz.Length-1; i>=0; i--)
    {
      builder.Append(sz[i]);
    }
    return builder.ToString();
}

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

Вы заметите, что я предоставил StringBuilder начальную емкость, которую вы не часто видите. Поскольку вы знаете длину результата для начала, это удаляет ненужные выделения памяти.

Что обычно происходит, это выделяет объем памяти для StringBuilder (по умолчанию 16 символов). Как только содержимое пытается превысить эту емкость, оно удваивает (я думаю) свою собственную емкость и продолжает. Это намного лучше, чем выделять память каждый раз, как это происходит с обычными строками, но если вы можете избежать этого, это даже лучше.

Answer 3

Несколько комментариев к ответам, данным до сих пор:

• Каждый из них (пока!) Потерпит неудачу на суррогатных парах и объединяющих персонажах. О, радости Юникода. Реверсирование строки - это не то же самое, что реверсирование последовательности символов.
• Мне нравится Оптимизация Марка для нулевого, пустого и односимвольного ввода. В частности, это не только быстро дает правильный ответ, но и обрабатывает нуль (чего не делают ни один из других ответов)
• Изначально я думал, что ToCharArray, за которым следует Array.Reverse, будет самым быстрым, но он создает одну «мусорную» копию.
• Решение StringBuilder создает одну строку (не массив символов) и манипулирует ею до тех пор, пока вы не вызовете ToString. Никакого дополнительного копирования не требуется ... но гораздо больше работы по поддержанию длины и т. Д.

Какое решение является более эффективным? Что ж, мне нужно сравнить его, чтобы иметь какое-либо представление, но даже в этом случае не будет рассказано всей истории. Вы используете это в ситуации с высоким давлением памяти, где лишний мусор - это настоящая боль? Как быстро ваша память против вашего процессора и т. Д.

Как всегда, читаемость обычно король - и это не намного лучше, чем ответ Марка на этом фронте. В частности, нет места для ошибки «один на один», тогда как мне нужно было бы подумать над проверкой других ответов. Я не люблю думать. Это вредит моему мозгу, поэтому я стараюсь не делать это очень часто. Использование встроенного Array.Reverse звучит для меня намного лучше. (Ладно, значит, он все еще не работает на суррогатах и ​​т. Д., Но эй ...)

Answer 4

Поскольку строки являются неизменяемыми, каждый оператор += создает новую строку путем копирования строки на последнем шаге вместе с одним символом для формирования новой строки. По сути, это будет алгоритм O (n ² ) вместо O (n).

Более быстрый способ будет (O (n)):

// pseudocode:
static string ReverseString(string input) {
    char[] buf = new char[input.Length];
    for(int i = 0; i < buf.Length; ++i)
       buf[i] = input[input.Length - i - 1];
    return new string(buf);
}

Answer 5

Вместо этого вы можете сделать это в .NET 3.5:

    public static string Reverse(this string s)
    {
        return new String((s.ToCharArray().Reverse()).ToArray());
    }

Answer 6

Этот метод сокращает количество итераций пополам. Вместо того, чтобы начинать с конца, он начинается с начала и меняет местами символы, пока не достигнет центра. Пришлось преобразовать строку в массив символов, потому что индексатор строки не имеет установщика.

    public string Reverse(String value)
    {
        if (String.IsNullOrEmpty(value)) throw new ArgumentNullException("value");

        char[] array = value.ToCharArray();

        for (int i = 0; i < value.Length / 2; i++)
        {
            char temp = array[i];
            array[i] = array[(array.Length - 1) - i];
            array[(array.Length - 1) - i] = temp;
        }

        return new string(array);
    }

Answer 7

x - строка для обратного.

        Stack<char> stack = new Stack<char>(x);

        string s = new string(stack.ToArray());

Answer 8

Я предпочитаю что-то вроде этого:

using System;
using System.Text;
namespace SpringTest3
{
    static class Extentions
    {
        static private StringBuilder ReverseStringImpl(string s, int pos, StringBuilder sb)
        {
            return (s.Length <= --pos || pos < 0) ? sb : ReverseStringImpl(s, pos, sb.Append(s[pos]));
        }

        static public string Reverse(this string s)
        {
            return ReverseStringImpl(s, s.Length, new StringBuilder()).ToString();
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("abc".Reverse());
        }
    }
}

Answer 9

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

Answer 10

Лучшим способом решения этой проблемы было бы использование StringBuilder, так как он не является неизменным, вы не получите ужасного поведения генерации объектов, которое вы могли бы получить выше. В .net все строки являются неизменяемыми, что означает, что оператор + = будет создавать новый объект при каждом нажатии. StringBuilder использует внутренний буфер, поэтому обращение может быть выполнено в буфере без дополнительных выделений объектов.