Строка.Присоединяйтесь и класса StringBuilder: что быстрее?


на предыдущий вопрос о форматировании a double[][] в формат CSV, Марк Gravell сказал что с помощью StringBuilder будет быстрее, чем String.Join. Это правда?

6 59

6 ответов:

короткий ответ: это зависит.

ответ: если у вас уже есть массив строк, чтобы объединить вместе (с разделителем), String.Join Это самый быстрый способ сделать это.

String.Join можно просмотреть все строки, чтобы определить точную длину, которая ему нужна, а затем снова перейти и скопировать все данные. Это значит, что будет нет дополнительное копирование участвует. Элемент только минус в том, что он должен пройти через строки в два раза, что означает потенциальный взрыв кэша памяти больше раз, чем это необходимо.

если вы не есть строки в виде массива заранее, это наверное быстрее использовать StringBuilder - но бывают ситуации, когда это не так. Если вы используете StringBuilder означает делать много-много копий, затем построить массив и затем вызвать String.Join вполне может быть быстрее.

EDIT: это с точки зрения одного вызова String.Join против куча звонков StringBuilder.Append. В исходном вопросе у нас было два разных уровня String.Join вызовы, поэтому каждый из вложенных вызовов создал бы промежуточную строку. Другими словами, это еще сложнее и сложнее угадать. Я был бы удивлен, увидев, что в любом случае" выиграть " значительно (в терминах сложности) с типичными данными.

EDIT: когда я буду дома, я напишу тест, который так же болезнен, как и для StringBuilder. В основном, если у вас есть массив, где каждый элемент около в два раза больше предыдущего, и вы получите его в самый раз, вы должны быть в состоянии заставить копию для каждого добавления (элементов, а не разделителя, хотя это тоже нужно учитывать). На тот момент это почти так же плохо, как простая конкатенация строк - но String.Join проблем не будет.

вот моя испытательная установка, используя int[][] для простоты; результаты первого:

Join: 9420ms (chk: 210710000
OneBuilder: 9021ms (chk: 210710000

(обновление для double результаты:)

Join: 11635ms (chk: 210710000
OneBuilder: 11385ms (chk: 210710000

(обновление re 2048 * 64 * 150)

Join: 11620ms (chk: 206409600
OneBuilder: 11132ms (chk: 206409600

и с включенным OptimizeForTesting:

Join: 11180ms (chk: 206409600
OneBuilder: 10784ms (chk: 206409600

так быстрее, но не массово; rig (запуск на консоли, в режиме выпуска и т. д.):

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Text;

namespace ConsoleApplication2
{
    class Program
    {
        static void Collect()
        {
            GC.Collect(GC.MaxGeneration, GCCollectionMode.Forced);
            GC.WaitForPendingFinalizers();
            GC.Collect(GC.MaxGeneration, GCCollectionMode.Forced);
            GC.WaitForPendingFinalizers();
        }
        static void Main(string[] args)
        {
            const int ROWS = 500, COLS = 20, LOOPS = 2000;
            int[][] data = new int[ROWS][];
            Random rand = new Random(123456);
            for (int row = 0; row < ROWS; row++)
            {
                int[] cells = new int[COLS];
                for (int col = 0; col < COLS; col++)
                {
                    cells[col] = rand.Next();
                }
                data[row] = cells;
            }
            Collect();
            int chksum = 0;
            Stopwatch watch = Stopwatch.StartNew();
            for (int i = 0; i < LOOPS; i++)
            {
                chksum += Join(data).Length;
            }
            watch.Stop();
            Console.WriteLine("Join: {0}ms (chk: {1}", watch.ElapsedMilliseconds, chksum);

            Collect();
            chksum = 0;
            watch = Stopwatch.StartNew();
            for (int i = 0; i < LOOPS; i++)
            {
                chksum += OneBuilder(data).Length;
            }
            watch.Stop();
            Console.WriteLine("OneBuilder: {0}ms (chk: {1}", watch.ElapsedMilliseconds, chksum);

            Console.WriteLine("done");
            Console.ReadLine();
        }
        public static string Join(int[][] array)
        {
            return String.Join(Environment.NewLine,
                    Array.ConvertAll(array,
                      row => String.Join(",",
                        Array.ConvertAll(row, x => x.ToString()))));
        }
        public static string OneBuilder(IEnumerable<int[]> source)
        {
            StringBuilder sb = new StringBuilder();
            bool firstRow = true;
            foreach (var row in source)
            {
                if (firstRow)
                {
                    firstRow = false;
                }
                else
                {
                    sb.AppendLine();
                }
                if (row.Length > 0)
                {
                    sb.Append(row[0]);
                    for (int i = 1; i < row.Length; i++)
                    {
                        sb.Append(',').Append(row[i]);
                    }
                }
            }
            return sb.ToString();
        }
    }
}

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

Я создал два метода тестирования, чтобы сравнить их:

public static string TestStringJoin(double[][] array)
{
    return String.Join(Environment.NewLine,
        Array.ConvertAll(array,
            row => String.Join(",",
                       Array.ConvertAll(row, x => x.ToString()))));
}

public static string TestStringBuilder(double[][] source)
{
    // based on Marc Gravell's code

    StringBuilder sb = new StringBuilder();
    foreach (var row in source)
    {
        if (row.Length > 0)
        {
            sb.Append(row[0]);
            for (int i = 1; i < row.Length; i++)
            {
                sb.Append(',').Append(row[i]);
            }
        }
    }
    return sb.ToString();
}

я запускал каждый метод 50 раз, передавая массив размера [2048][64]. Я сделал это для двух массивов; один заполнен нулями, а другой-случайными значениями. У меня есть ... следующие результаты на моей машине (P4 3.0 GHz, одноядерный, без HT, работает режим выпуска из CMD):

// with zeros:
TestStringJoin    took 00:00:02.2755280
TestStringBuilder took 00:00:02.3536041

// with random values:
TestStringJoin    took 00:00:05.6412147
TestStringBuilder took 00:00:05.8394650

увеличение размера массива до [2048][512], при уменьшении числа итераций до 10 получил следующие результаты:

// with zeros:
TestStringJoin    took 00:00:03.7146628
TestStringBuilder took 00:00:03.8886978

// with random values:
TestStringJoin    took 00:00:09.4991765
TestStringBuilder took 00:00:09.3033365

результаты повторяемы (почти; с небольшими флуктуациями, вызванными различными случайными значениями). Видимо String.Join немного быстрее большую часть времени (хотя и с очень небольшим отрывом).

это код, который я используется для тестирования:

const int Iterations = 50;
const int Rows = 2048;
const int Cols = 64; // 512

static void Main()
{
    OptimizeForTesting(); // set process priority to RealTime

    // test 1: zeros
    double[][] array = new double[Rows][];
    for (int i = 0; i < array.Length; ++i)
        array[i] = new double[Cols];

    CompareMethods(array);

    // test 2: random values
    Random random = new Random();
    double[] template = new double[Cols];
    for (int i = 0; i < template.Length; ++i)
        template[i] = random.NextDouble();

    for (int i = 0; i < array.Length; ++i)
        array[i] = template;

    CompareMethods(array);
}

static void CompareMethods(double[][] array)
{
    Stopwatch stopwatch = Stopwatch.StartNew();
    for (int i = 0; i < Iterations; ++i)
        TestStringJoin(array);
    stopwatch.Stop();
    Console.WriteLine("TestStringJoin    took " + stopwatch.Elapsed);

    stopwatch.Reset(); stopwatch.Start();
    for (int i = 0; i < Iterations; ++i)
        TestStringBuilder(array);
    stopwatch.Stop();
    Console.WriteLine("TestStringBuilder took " + stopwatch.Elapsed);

}

static void OptimizeForTesting()
{
    Thread.CurrentThread.Priority = ThreadPriority.Highest;
    Process currentProcess = Process.GetCurrentProcess();
    currentProcess.PriorityClass = ProcessPriorityClass.RealTime;
    if (Environment.ProcessorCount > 1) {
        // use last core only
        currentProcess.ProcessorAffinity
            = new IntPtr(1 << (Environment.ProcessorCount - 1));
    }
}

Если разница в 1% не превращается во что-то значительное с точки зрения времени, которое требуется для запуска всей программы, это выглядит как микро-оптимизация. Я бы написал код, который является наиболее читаемым / понятным и не беспокоится о разнице в производительности 1%.

У Этвуда был пост, связанный с этим около месяца назад:

http://www.codinghorror.com/blog/archives/001218.html

да. Если вы сделаете больше, чем пару соединений, это будет много быстрее.

когда вы делаете строку.присоединяйтесь, среда выполнения должна:

  1. выделить память для результирующей строки
  2. скопируйте содержимое первой строки в начало выходной строки
  3. скопировать содержимое второй строки в конец выходной строки.

Если вы делаете два соединения, он должен скопировать данные дважды, и так на.

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