String.Join vs. StringBuilder: que é mais rápido?
https://stackoverflow.com/questions/585860
-
06-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Em um anterior pergunta sobre a formatação de um double[][] para formato CSV, foi sugerido que o uso de StringBuilder seria mais rápido do que String.Join. Isso é verdade?
Solução
Resposta curta:. Isso depende
Long resposta:. se você já tem uma matriz de strings para concatenar juntos (com um delimitador), String.Join é a maneira mais rápida de fazê-lo
String.Join pode olhar através de todas as cordas para trabalhar fora o comprimento exato que precisa, em seguida, ir novamente e copiar todos os dados. Isso significa que não será não cópia extra envolvido. O única desvantagem é que ele tem que passar as cordas duas vezes, o que significa potencialmente soprando o cache de memória mais vezes do que o necessário.
Se você não tem as cordas como uma matriz de antemão, é provavelmente mais rápido para uso StringBuilder - mas haverá situações em que não é. Se estiver usando um meio StringBuilder fazendo lotes e lotes de cópias, em seguida, construir uma matriz e, em seguida, chamando String.Join pode muito bem ser mais rápido.
EDIT: Este é, em termos de uma única chamada para String.Join vs um monte de chamadas para StringBuilder.Append. Na pergunta original, tivemos dois níveis diferentes de chamadas String.Join, então cada uma das chamadas aninhadas teria criado uma cadeia intermediária. Em outras palavras, é ainda mais complexo e mais difícil de adivinhar. Eu ficaria surpreso de ver uma ou outra maneira "ganhar" significativamente (em termos de complexidade) com dados típicos.
EDIT: Quando eu estou em casa, eu vou escrever-se um ponto de referência que é tão doloroso como possivelmente para StringBuilder. Basicamente, se você tiver uma matriz onde cada elemento é o dobro do tamanho do anterior, e você obtê-lo apenas para a direita, você deve ser capaz de forçar uma cópia para cada acréscimo (de elementos, não do delimitador, embora que precisa ser tidos em conta também). Nesse ponto, é quase tão ruim quanto simples concatenação -. Mas String.Join não terá problemas
Outras dicas
Aqui está o meu equipamento de teste, usando int[][] pela simplicidade; resultados do primeiro:
Join: 9420ms (chk: 210710000
OneBuilder: 9021ms (chk: 210710000
(atualização para resultados double:)
Join: 11635ms (chk: 210710000
OneBuilder: 11385ms (chk: 210710000
(update re 2048 * 64 * 150)
Join: 11620ms (chk: 206409600
OneBuilder: 11132ms (chk: 206409600
e com OptimizeForTesting ativado:
Join: 11180ms (chk: 206409600
OneBuilder: 10784ms (chk: 206409600
Assim, mais rápido, mas não maciçamente assim; rig (executado na consola, no modo de versão, etc):
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();
}
}
}
Eu não penso assim. Olhando através do refletor, a implementação de olhares String.Join muito otimizado. Ele também tem a vantagem de saber o tamanho total da cadeia a ser criado com antecedência, por isso não precisa de qualquer realocação.
Eu criei dois métodos de ensaio para compará-los:
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();
}
corri cada método 50 vezes, passando em uma matriz de tamanho [2048][64]. Eu fiz isso por duas matrizes; um preenchido com zeros e outro cheio com valores aleatórios. Eu tenho os seguintes resultados na minha máquina (P4 3.0 GHz, single-core, não HT, que funcionam de modo lançamento de 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
O aumento do tamanho da matriz para [2048][512], ao diminuir o número de iterações a 10 me tem os seguintes resultados:
// 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
Os resultados são reprodutíveis (quase, com pequenas flutuações causadas por diferentes valores aleatórios). Aparentemente String.Join é um pouco mais rápido na maioria das vezes (embora por uma margem muito pequena).
Este é o código que usei para testar:
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));
}
}
A menos que as voltas 1% de diferença em algo significativo em termos de tempo todo o programa leva para executar, isso parece micro-otimização. Eu ia escrever o código que é a preocupação mais legível / compreensível e não sobre a diferença de desempenho de 1%.
Atwood tinha uma espécie cargo de relacionado a este cerca de um mês atrás:
Sim. Se você fazer mais do que um par de junta, será muito mais rápido.
Quando você faz uma string.join, o tempo de execução deve:
- Alocar memória para a cadeia resultante
- copiar o conteúdo da primeira corda para o início da cadeia de saída
- copiar o conteúdo da segunda cadeia para o fim da cadeia de saída.
Se você fizer dois junta-se, tem que copiar os dados duas vezes, e assim por diante.
StringBuilder atribui uma memória intermédia com espaço para reposição, de modo que os dados podem ser acrescentadas sem ter de copiar a cadeia original. Como não há espaço deixado no tampão, a cadeia anexa pode ser escrito na memória intermédia directamente. Em seguida, ele só tem que copiar toda a cadeia uma vez, no final.
