Струны соединения и сложности?

Question

Когда мне нужно соединить две строки, я использую String.Format (или StringBuilder, если это происходит в нескольких местах кода).

Я вижу, что некоторые хорошие программисты не обращают внимания на сложность строк и просто используют оператор '+'.

Я знаю, что использование оператора '+' заставляет приложение использовать больше памяти, но как насчет сложности?

Answer 1

Это отличная статья о наших собственных методах объединения строк Джефф Этвуд on Coding Horror :

_{(источник: codinghorror.com )}

Печальная трагедия театра микрооптимизации

Вот суть поста.

[ показано несколько методов объединения строк ]

Возьми свой зудящий маленький курок от этого ключа компиляции и думать о это на минуту. Какой из них методы будут быстрее?

Получил ответ? Отлично!

и .. барабанная дробь пожалуйста .. правильная ответ:

It. Просто. Не имеет. Matter!

Answer 2

В этом ответе предполагается, что вы говорите о сложности времени выполнения.

Использование + создает новый строковый объект, что означает, что содержимое обоих старых строковых объектов должно быть скопировано в новый. При большом количестве конкатенации, например в узком цикле, это может превратиться в операцию O (n ^ 2).

В качестве неофициального доказательства, скажем, у вас был следующий код:

string foo = "a";
for(int i = 0; i < 1000; i++)
{
    foo += "a";
}

Первая итерация цикла, сначала содержимое foo ("a") копируется в новый строковый объект, затем содержимое литерала "a". Это две копии. Вторая итерация имеет три копии; два из нового foo и один из буквального «а». 1000-я итерация будет иметь 1001 операцию копирования. Общее количество копий составляет 2 + 3 + ... + 1001. В общем, если в цикле вы объединяете только один символ в каждой итерации (и начинаете с одного символа в длину), если число итераций равно n, будет 2 + 3 + ... + n + 1 копий. Это то же самое, что и 1 + 2 + 3 + ... + n = n(n+1)/2 = (n^2 + n)/2, то есть O (n ^ 2).

Answer 3

Поскольку строки неизменяемы в таких языках, как Java и C #, каждый раз при объединении двух строк необходимо создавать новую строку, в которую копируется содержимое двух старых строк.

Допустим, строки длиной в среднем c символами.

Теперь первая конкатенация должна копировать только 2 * c символа, но последняя должна копировать конкатенацию первых n-1 строк длиной (n-1) * c символов и самой последней. , длиной c символов, всего n * c символов. Для n конкатенаций это составляет n ^ 2 * c / 2 символов, что означает алгоритмическую сложность O (n ^ 2).

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

Однако есть случаи, когда это имеет значение, и использование O (n ^ 2) в таких случаях может быть смертельным.

На практике я видел это, например, для генерации больших файлов Word XML в памяти, включая изображения в кодировке base64. Это поколение занимало более 10 минут из-за конкатенации строк O (n ^ 2). После того как я заменил конкатенацию с помощью + на StringBuilder, время выполнения для того же документа сократилось до 10 секунд.

Точно так же я видел часть программного обеспечения, которая генерировала невероятно большой кусок кода SQL в виде строки, использующей + для конкатенации. Я даже не ждал, пока это закончится (ждал уже более часа), но просто переписал его с помощью StringBuilder. Эта более быстрая версия завершилась в течение минуты.

Короче говоря, просто делайте то, что наиболее читабельно / проще всего написать, и думайте об этом только тогда, когда вы будете создавать чертову огромную строку: -)

Answer 4

Если ваше приложение не является слишком интенсивным (профиль, профиль, профиль!), Это не имеет значения. Хорошие программисты ставят читабельность выше производительности для мирских операций.

Answer 5

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

Answer 6

Я думаю, что с точки зрения сложности вы торгуете повторением вновь созданных строк для разбора строки формата. Для axample "A" + "B" + "C" + "D" означает, что вам нужно скопировать «A», «AB» и, наконец, «ABC», чтобы сформировать «ABCD». Копирование - это повторение, верно? Так, например, если у вас есть строка из 1000 символов, которую вы будете суммировать с тысячами строк из одного символа, вы скопируете (1000 + N) строк символов 1000 раз . Это приводит к сложности O (n ^ 2) в худших случаях.

Strin.Fomat , даже с учетом синтаксического анализа, и StringBuffer должно быть около O (n).

Answer 7

Если вы используете «+» только один раз, у вас нет от этого недостатка, и это повышает удобочитаемость (как уже говорил Колин Пикард).

Насколько я знаю + означает: взять левый операнд и правый операнд и скопировать их в новый буфер (так как строки неизменяемы).

Таким образом, используя + два раза (как в примере с Colin Pickards, вы уже создали 2 временных строки. Сначала при добавлении "<p>" к вступлению, а затем при добавлении "</p>" к вновь созданной строке.

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

Answer 8

Зависит от ситуации. + Иногда может уменьшить сложность кода. Рассмотрим следующий код:

output = "<p>" + intro + "</p>";

Это хорошая, четкая линия. Формат строки не требуется.

Answer 9

Я тестировал это всегда, и со времени .NET 1.0 или 1.1 это не изменилось.

Тогда, если бы у вас был какой-то процесс, который собирался выполнить несколько строк кода, объединяющих строки, вы могли бы получить огромное увеличение скорости, используя String.Concat, String.Format или StringBuilder.

Теперь это не имеет значения вообще. По крайней мере, это не имело значения с тех пор, как вышел .Net 2.0. Уберите это из головы и запишите любой код, чтобы вам было легче читать.

Answer 10

Компилятор оптимизирует конкатенацию строкового литерала в один строковый литерал. Например:

string s = "a" + "b" + "c";

оптимизируется для следующего во время компиляции:

string s = "abc";

См. этот вопрос и эту статью MSDN для получения дополнительной информации.