Оптимизация строковых операций в C#

Используйте StringBuilder для объединения более (приблизительно) 5 строк (результаты могут незначительно отличаться). Также дайте конструктору StringBuilder подсказку об ожидаемом максимальном размере.

[Обновление]: просто комментирую ваши изменения в вопросе. Вы также можете повысить производительность StringBuilder, если у вас есть приблизительное (или точное) представление об окончательном размере объединенных строк, потому что это уменьшит количество выделений памяти, которые он должен выполнить:

// e.g. Initialise to 10MB
StringBuilder fraction = new StringBuilder(10000000);

Also, on a related topic, I've heard it said that you should never use the + operator with strings, in favour of string.Format(), is this true?

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

Что касается вашего кода ... он приводит к копированию строк меньшего размера (а именно, tmp) при конкатенации. Конечно, в fraction += tmp вы копируете строку большего размера, но это происходит реже.

Таким образом, вы уменьшили много больших копий до нескольких больших и многих маленьких копий.

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

Я не могу сейчас проводить тесты, но попробую использовать StringBuilder.

int i = 1;
    StringBuilder fraction = new StringBuilder();
    while (fraction.Length < 1000000)
    {
        fraction.Append(i);
        i++;
    }
return sb.ToString();

Вы, вероятно, увидите, что первые 1000 символов почти не занимают времени, в отличие от последних 1000 символов.

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

Вашу оптимизацию легко сравнить с тем, что вы обычно делаете с потоками, если вы используете буфер. Большие фрагменты обычно приводят к повышению производительности до тех пор, пока вы не достигнете критического размера, когда он больше не имеет никакого значения, и начинает быть недостатком, когда вы обрабатываете небольшие объемы данных.

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

Я вообще не получаю твоих результатов. В моем случае StringBuilder выигрывает. Не могли бы вы выложить полную программу тестирования? Вот мой, с тремя вариантами: оптимизация конкатенации строк, «простой» StringBuilder и StringBuilder с начальной емкостью. Я увеличил лимит, так как на моем ящике он двигался слишком быстро, чтобы его можно было измерить.

using System;
using System.Diagnostics;
using System.Text;

public class Test
{
    const int Limit = 4000000;

    static void Main()
    {
        Time(Concatenation, "Concat");
        Time(SimpleStringBuilder, "StringBuilder as in post");
        Time(SimpleStringBuilderNoToString, "StringBuilder calling Append(i)");
        Time(CapacityStringBuilder, "StringBuilder with appropriate capacity");
    }

    static void Time(Action action, string name)
    {
        Stopwatch sw = Stopwatch.StartNew();
        action();
        sw.Stop();
        Console.WriteLine("{0}: {1}ms", name, sw.ElapsedMilliseconds);
        GC.Collect();
        GC.WaitForPendingFinalizers();
    }

    static void Concatenation()
    {
        int i = 1;
        string fraction = "";
        while (fraction.Length < Limit)
        {
            // concatenating strings is much faster for small strings
            string tmp = "";
            for (int j = 0; j < 1000; j++)
            {
                tmp += i.ToString();
                i++;
            }
            fraction += tmp;            
        }
    }

    static void SimpleStringBuilder()
    {
        int i = 1;
        StringBuilder fraction = new StringBuilder();
        while (fraction.Length < Limit)
        {
            fraction.Append(i.ToString());
            i++;
        }
    }

    static void SimpleStringBuilderNoToString()
    {
        int i = 1;
        StringBuilder fraction = new StringBuilder();
        while (fraction.Length < Limit)
        {
            fraction.Append(i);
            i++;
        }
    }

    static void CapacityStringBuilder()
    {
        int i = 1;
        StringBuilder fraction = new StringBuilder(Limit + 10);
        while (fraction.Length < Limit)
        {
            fraction.Append(i);
            i++;
        }
    }
}

И результаты:

Concat: 5879ms
StringBuilder as in post: 206ms
StringBuilder calling Append(i): 196ms
StringBuilder with appropriate capacity: 184ms

Причина, по которой ваша конкатенация выполняется быстрее, чем самое первое решение, проста - вы выполняете несколько «дешевых» конкатенаций (при которых каждый раз копируется относительно мало данных) и относительно небольшое количество «больших» конкатенаций (пока что для всей строки) . В оригинале каждый шаг копирует все данные, полученные на данный момент, что, очевидно, дороже.

Ответ на измененный квестон («почему эта неочевидная оптимизация так хорошо работает» и «правда ли, что не следует использовать оператор + для строк»):

Я не уверен, о какой неочевидной оптимизации вы говорите. Но ответ на второй вопрос, я думаю, охватывает все основы.

В C# строки работают так, что они выделяются как фиксированная длина и не могут быть изменены. Это означает, что каждый раз, когда вы пытаетесь изменить длину строки, создается целая новая строка, а старая строка копируется до нужной длины. Очевидно, это медленный процесс. Когда вы используете String.Format, он внутренне использует StringBuilder для создания строки.

StringBuilders работают с использованием буфера памяти, который распределяется более разумно, чем строки фиксированной длины, и поэтому в большинстве ситуаций работает значительно лучше. Я не уверен в деталях StringBuilder внутри компании, поэтому вам придется задать для этого новый вопрос. Я могу предположить, что он либо не перераспределяет старые части строки (вместо этого создает связанный список внутри и только фактически выделяет окончательный вывод, когда это необходимо ToString), либо перераспределяется с экспоненциальным ростом (когда ему не хватает памяти, он выделяет вдвое больше в следующий раз, таким образом, для строки размером 2 ГБ потребуется перераспределить всего около 30 раз).

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

Добавление символа в строку может иметь два последствия:

• если еще есть место для символа, он просто добавляется в конце; (как заметил комментатор, этого не может произойти со строками C#, поскольку они неизменны).
• если в конце нет места, для новой строки выделяется новый блок памяти, туда копируется содержимое старой строки и добавляется символ.

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

Затем в ситуации, когда дополнительное пространство не зарезервировано, в первом примере необходимо выполнить 1000000 выделений и копий в среднем 0,5 * 1000000 символов. Второй должен сделать 1000 выделений и копий в среднем 0,5 * 1000000 символов и 1000000 выделений и копий 0,5 * 1000 символов. Если копирование выполняется линейно с размером копии и свободным от размещения, первая ситуация занимает 500 000 000 000 единиц времени, а вторая - 500 000 000 + 500 000 000 единиц времени.