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

Question

Выполнение следующего кода C # занимает 5 минут:

int i = 1;
string fraction = "";
while (fraction.Length < 1000000)
{
    fraction += i.ToString();
    i++;
}

«Оптимизация», как это, заставляет его работать за 1,5 секунды:

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

РЕДАКТИРОВАТЬ: Некоторые люди предложили использовать StringBuilder, что также является отличным предложением, и это выходит на 0,06 с:

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

Игра в поисках оптимального значения j - тема для другого времени, но почему именно эта неочевидная оптимизация работает так хорошо? Кроме того, по смежной теме я слышал, что никогда не следует использовать оператор + со строками в пользу string.Format(), это правда?

Answer 1

Я не получаю ваши результаты вообще. На моей коробке 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

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

Answer 2

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

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

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

Answer 3

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

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

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

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

Answer 4

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

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

Answer 5

Кроме того, в смежной теме я слышал, что никогда не следует использовать оператор + со строками в пользу string.Format (), это правда?

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

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

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

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

Answer 6

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

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

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

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

Answer 7

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

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

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

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

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