una - stringbuilder replace c#

Eficiencia de la memoria y rendimiento de String.Replace.NET Framework

Question

 string str1 = "12345ABC...//...ABC100000"; 
 // Hypothetically huge string of 100000 + Unicode Chars
 str1 = str1.Replace("1", string.Empty);
 str1 = str1.Replace("22", string.Empty);
 str1 = str1.Replace("656", string.Empty);
 str1 = str1.Replace("77ABC", string.Empty);

 // ...  this replace anti-pattern might happen with upto 50 consecutive lines of code.

 str1 = str1.Replace("ABCDEFGHIJD", string.Empty);

He heredado un código que hace lo mismo que el fragmento anterior. Toma una cadena enorme y reemplaza (elimina) cadenas constantes más pequeñas de la cadena grande.

Creo que este es un proceso muy intensivo en memoria dado que nuevas cadenas inmutables grandes se asignan en la memoria para cada reemplazo, en espera de la muerte a través del GC.

1. ¿Cuál es la forma más rápida de reemplazar estos valores, ignorando las preocupaciones sobre la memoria?

2. ¿Cuál es la forma más eficiente de memoria de lograr el mismo resultado?

¡Espero que sean la misma respuesta!

Las soluciones prácticas que encajan en algún punto entre estos objetivos también son apreciadas.

Suposiciones

• Todos los reemplazos son constantes y conocidos de antemano
• Los personajes subyacentes contienen algunos caracteres unicode [no ascii]

Answer 1

Aquí está mi benchmark :

using System;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;

internal static class MeasureTime
{
    internal static TimeSpan Run(Action func, uint count = 1)
    {
        if (count == 0)
        {
            throw new ArgumentOutOfRangeException("count", "Must be greater than zero");
        }

        long[] arr_time = new long[count];
        Stopwatch sw = new Stopwatch();
        for (uint i = 0; i < count; i++)
        {
            sw.Start();
            func();
            sw.Stop();
            arr_time[i] = sw.ElapsedTicks;
            sw.Reset();
        }

        return new TimeSpan(count == 1 ? arr_time.Sum() : Convert.ToInt64(Math.Round(arr_time.Sum() / (double)count)));
    }
}

public class Program
{
    public static string RandomString(int length)
    {
        Random random = new Random();
        const string chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
        return new String(Enumerable.Range(1, length).Select(_ => chars[random.Next(chars.Length)]).ToArray());
    }

    public static void Main()
    {
        string rnd_str = RandomString(500000);
        Regex regex = new Regex("a|c|e|g|i|k", RegexOptions.Compiled);
        TimeSpan ts1 = MeasureTime.Run(() => regex.Replace(rnd_str, "!!!"), 10);
        Console.WriteLine("Regex time: {0:hh//:mm//:ss//:fff}", ts1);

        StringBuilder sb_str = new StringBuilder(rnd_str);
        TimeSpan ts2 = MeasureTime.Run(() => sb_str.Replace("a", "").Replace("c", "").Replace("e", "").Replace("g", "").Replace("i", "").Replace("k", ""), 10);
        Console.WriteLine("StringBuilder time: {0:hh//:mm//:ss//:fff}", ts2);

        TimeSpan ts3 = MeasureTime.Run(() => rnd_str.Replace("a", "").Replace("c", "").Replace("e", "").Replace("g", "").Replace("i", "").Replace("k", ""), 10);
        Console.WriteLine("String time: {0:hh//:mm//:ss//:fff}", ts3);
    }
}

Tiempo de Regex: 00: 00: 00: 008

Tiempo de StringBuilder: 00: 00: 00: 015

Tiempo de cadena: 00: 00: 00: 005

String.Replace es el más rápido

Answer 2

Aquí hay un punto de referencia rápido ...

        Stopwatch s = new Stopwatch();
        s.Start();
        string replace = source;
        replace = replace.Replace("$TS$", tsValue);
        replace = replace.Replace("$DOC$", docValue);
        s.Stop();

        Console.WriteLine("String.Replace:/t/t" + s.ElapsedMilliseconds);

        s.Reset();

        s.Start();
        StringBuilder sb = new StringBuilder(source);
        sb = sb.Replace("$TS$", tsValue);
        sb = sb.Replace("$DOC$", docValue);
        string output = sb.ToString();
        s.Stop();

        Console.WriteLine("StringBuilder.Replace:/t/t" + s.ElapsedMilliseconds);

No vi mucha diferencia en mi máquina (string.replace era de 85ms y stringbuilder.replace era 80), y eso estaba en contra de aproximadamente 8MB de texto en "fuente" ...

Answer 3

Como tiene múltiples reemplazos en una cadena, le recomiendo que use RegEx sobre StringBuilder.

Answer 4

Si quieres ser realmente rápido, y quiero decir realmente rápido, tendrás que mirar más allá del StringBuilder y simplemente escribir un código bien optimizado.

Una cosa que no le gusta a su computadora es ramificarse, si puede escribir un método de reemplazo que opera en una matriz fija (char *) y no se ramifica, tiene un gran rendimiento.

Lo que harás es que la operación de reemplazo buscará una secuencia de caracteres y, si encuentra alguna subcadena, la reemplazará. En efecto, copiará la cadena y al hacerlo, preformará la búsqueda y la reemplazará.

Confiarás en estas funciones para elegir el índice de algún buffer para leer / escribir. El objetivo es preformar el método de reemplazo de modo que cuando nada tenga que cambiar, escriba basura en lugar de ramificar.

Debería poder completar esto sin una sola instrucción if y recordar usar código inseguro. De lo contrario, pagará por la verificación del índice para cada acceso a los elementos.

unsafe
{
    fixed( char * p = myStringBuffer )
    {
        // Do fancy string manipulation here
    }
}

He escrito código como este en C # por diversión y he visto mejoras significativas en el rendimiento, casi un 300% de aceleración para buscar y reemplazar. Si bien .NET BCL (biblioteca de clases base) funciona bastante bien, está plagado de construcciones de bifurcación y manejo de excepciones, esto ralentizará tu código si usas las funciones incorporadas. Además, el compilador JIT no lleva a cabo estas optimizaciones mientras el sonido es perfecto, y tendrá que ejecutar el código como una versión de lanzamiento sin ningún tipo de depurador conectado para poder observar la ganancia de rendimiento masivo.

Podría proporcionarle un código más completo pero es una gran cantidad de trabajo. Sin embargo, puedo garantizarle que será más rápido que cualquier otra cosa sugerida hasta ahora.

Answer 5

StringBuilder: http://msdn.microsoft.com/en-us/library/2839d5h5.aspx

El rendimiento de la operación Reemplazar debe ser aproximadamente el mismo que el de cadena. Reemplazar y, según Microsoft, no se debe producir basura.

Answer 6

si quieres una clase incorporada en dotnet, creo que StringBuilder es el mejor. para hacerlo manualmente puede usar código inseguro con char * e iterar a través de su cadena y reemplazarlo según sus criterios

Answer 7

Todos los caracteres en una cadena .NET son "caracteres unicode". ¿Quieres decir que no son ascii? Eso no debería representar ninguna desventaja, a menos que se encuentre con problemas de composición, por ejemplo, un "acento agudo e +" que no se reemplaza cuando intenta reemplazar un "agudo".

Podría intentar usar una expresión regular con Regex.Replace o StringBuilder.Replace . Aquí hay un código de muestra que hace lo mismo con ambos:

using System;
using System.Text;
using System.Text.RegularExpressions;

class Test
{
    static void Main(string[] args)
    {
        string original = "abcdefghijkl";

        Regex regex = new Regex("a|c|e|g|i|k", RegexOptions.Compiled);

        string removedByRegex = regex.Replace(original, "");
        string removedByStringBuilder = new StringBuilder(original)
            .Replace("a", "")
            .Replace("c", "")
            .Replace("e", "")
            .Replace("g", "")
            .Replace("i", "")
            .Replace("k", "")
            .ToString();

        Console.WriteLine(removedByRegex);
        Console.WriteLine(removedByStringBuilder);
    }
}

No me gustaría adivinar cuál es más eficiente. Tendría que comparar con su aplicación específica. La forma regex puede ser capaz de hacerlo todo de una vez, pero ese pase será relativamente intensivo en CPU en comparación con cada una de las muchas sustituciones en StringBuilder.

Answer 8

1. ¿Cuál es la forma más rápida de reemplazar estos valores, ignorando las preocupaciones sobre la memoria?

La manera más rápida es crear un componente personalizado que sea específico para su caso de uso. A partir de .NET 4.6, no hay clases en el BCL diseñadas para reemplazos de cadenas múltiples.

Si NECESITA algo rápido fuera del BCL, StringBuilder es el componente BCL más rápido para el reemplazo simple de cadenas. El código fuente se puede encontrar here : es bastante eficiente para reemplazar una sola cadena. Solo use Regex si realmente necesita el poder de coincidencia de patrones de las expresiones regulares. Es más lento y un poco más engorroso, incluso cuando se compila.

2. ¿Cuál es la forma más eficiente de memoria de lograr el mismo resultado?

La forma más eficiente de la memoria es realizar una copia de la secuencia filtrada desde el origen hasta el destino (se explica a continuación). El consumo de memoria se limitará a su búfer, sin embargo, esto requerirá más CPU; como regla general, intercambiará el rendimiento de la CPU por el consumo de memoria.

Detalles técnicos

Los reemplazos de cadena son complicados. Incluso cuando se realiza un reemplazo de cadena en un espacio de memoria mutable (como con StringBuilder ), es costoso. Si la cadena de reemplazo tiene una longitud diferente a la cadena original, reubicarás a cada personaje siguiendo la cadena de reemplazo para mantener toda la cadena contigua. Esto da como resultado MUCHAS escrituras de memoria, e incluso en el caso de StringBuilder , hace que reescriba la mayor parte de la cadena en la memoria en cada llamada a Reemplazar.

Entonces, ¿cuál es la forma más rápida de hacer reemplazos de cuerdas? Escriba la nueva cadena con una sola pasada: no permita que su código retroceda y tenga que volver a escribir nada. Las escrituras son más caras que las lecturas. Tendrás que codificarlo tú mismo para obtener mejores resultados.

Solución de alta memoria

La clase que he escrito genera cadenas basadas en plantillas. Pongo tokens ($ ReplaceMe $) en una plantilla que marca los lugares donde quiero insertar una cadena más tarde. Lo uso en casos donde XmlWriter es demasiado oneroso para XML que es en gran parte estático y repetitivo, y necesito producir grandes flujos de datos XML (o JSON).

La clase funciona dividiendo la plantilla en partes y coloca cada parte en un diccionario numerado. Los parámetros también están enumerados. El orden en el que las partes y los parámetros se insertan en una nueva cadena se colocan en una matriz entera. Cuando se genera una nueva cadena, las partes y los parámetros se seleccionan del diccionario y se usan para crear una nueva cadena.

No está completamente optimizado ni es a prueba de balas, pero funciona muy bien para generar flujos de datos muy grandes desde las plantillas.

Solución de baja memoria

Deberá leer pequeños fragmentos de la cadena de origen en un búfer, buscar en el búfer utilizando un algoritmo de búsqueda optimizado y luego escribir la nueva cadena en el flujo / secuencia de destino. Aquí hay muchas posibles limitaciones, pero sería eficiente en cuanto a la memoria y una mejor solución para los datos de origen que son dinámicos y no pueden almacenarse en caché, como traducciones de página completa o datos de origen que son demasiado grandes para caché razonable. No tengo una solución de muestra para este práctico.

Código de muestra

Resultados deseados

<DataTable source=''Users''>
  <Rows>
    <Row id=''25'' name=''Administrator'' />
    <Row id=''29'' name=''Robert'' />
    <Row id=''55'' name=''Amanda'' />
  </Rows>
</DataTable>

Modelo

<DataTable source=''$TableName$''>
  <Rows>
    <Row id=''$0$'' name=''$1$''/>
  </Rows>
</DataTable>

Caso de prueba

class Program
{
  static string[,] _users =
  {
    { "25", "Administrator" },
    { "29", "Robert" },
    { "55", "Amanda" },
  };

  static StringTemplate _documentTemplate = new StringTemplate(@"<DataTable source=''$TableName$''><Rows>$Rows$</Rows></DataTable>");
  static StringTemplate _rowTemplate = new StringTemplate(@"<Row id=''$0$'' name=''$1$'' />");
  static void Main(string[] args)
  {
    _documentTemplate.SetParameter("TableName", "Users");
    _documentTemplate.SetParameter("Rows", GenerateRows);

    Console.WriteLine(_documentTemplate.GenerateString(4096));
    Console.ReadLine();
  }

  private static void GenerateRows(StreamWriter writer)
  {
    for (int i = 0; i <= _users.GetUpperBound(0); i++)
      _rowTemplate.GenerateString(writer, _users[i, 0], _users[i, 1]);
  }
}

Fuente StringTemplate

public class StringTemplate
{
  private string _template;
  private string[] _parts;
  private int[] _tokens;
  private string[] _parameters;
  private Dictionary<string, int> _parameterIndices;
  private string[] _replaceGraph;
  private Action<StreamWriter>[] _callbackGraph;
  private bool[] _graphTypeIsReplace;

  public string[] Parameters
  {
    get { return _parameters; }
  }

  public StringTemplate(string template)
  {
    _template = template;
    Prepare();
  }

  public void SetParameter(string name, string replacement)
  {
    int index = _parameterIndices[name] + _parts.Length;
    _replaceGraph[index] = replacement;
    _graphTypeIsReplace[index] = true;
  }

  public void SetParameter(string name, Action<StreamWriter> callback)
  {
    int index = _parameterIndices[name] + _parts.Length;
    _callbackGraph[index] = callback;
    _graphTypeIsReplace[index] = false;
  }

  private static Regex _parser = new Regex(@"/$(/w{1,64})/$", RegexOptions.Compiled);
  private void Prepare()
  {
    _parameterIndices = new Dictionary<string, int>(64);
    List<string> parts = new List<string>(64);
    List<object> tokens = new List<object>(64);
    int param_index = 0;
    int part_start = 0;

    foreach (Match match in _parser.Matches(_template))
    {
      if (match.Index > part_start)
      {
        //Add Part
        tokens.Add(parts.Count);
        parts.Add(_template.Substring(part_start, match.Index - part_start));
      }


      //Add Parameter
      var param = _template.Substring(match.Index + 1, match.Length - 2);
      if (!_parameterIndices.TryGetValue(param, out param_index))
        _parameterIndices[param] = param_index = _parameterIndices.Count;
      tokens.Add(param);

      part_start = match.Index + match.Length;
    }

    //Add last part, if it exists.
    if (part_start < _template.Length)
    {
      tokens.Add(parts.Count);
      parts.Add(_template.Substring(part_start, _template.Length - part_start));
    }

    //Set State
    _parts = parts.ToArray();
    _tokens = new int[tokens.Count];

    int index = 0;
    foreach (var token in tokens)
    {
      var parameter = token as string;
      if (parameter == null)
        _tokens[index++] = (int)token;
      else
        _tokens[index++] = _parameterIndices[parameter] + _parts.Length;
    }

    _parameters = _parameterIndices.Keys.ToArray();
    int graphlen = _parts.Length + _parameters.Length;
    _callbackGraph = new Action<StreamWriter>[graphlen];
    _replaceGraph = new string[graphlen];
    _graphTypeIsReplace = new bool[graphlen];

    for (int i = 0; i < _parts.Length; i++)
    {
      _graphTypeIsReplace[i] = true;
      _replaceGraph[i] = _parts[i];
    }
  }

  public void GenerateString(Stream output)
  {
    var writer = new StreamWriter(output);
    GenerateString(writer);
    writer.Flush();
  }

  public void GenerateString(StreamWriter writer)
  {
    //Resolve graph
    foreach(var token in _tokens)
    {
      if (_graphTypeIsReplace[token])
        writer.Write(_replaceGraph[token]);
      else
        _callbackGraph[token](writer);
    }
  }

  public void SetReplacements(params string[] parameters)
  {
    int index;
    for (int i = 0; i < _parameters.Length; i++)
    {
      if (!Int32.TryParse(_parameters[i], out index))
        continue;
      else
        SetParameter(index.ToString(), parameters[i]);
    }
  }

  public string GenerateString(int bufferSize = 1024)
  {
    using (var ms = new MemoryStream(bufferSize))
    {
      GenerateString(ms);
      ms.Position = 0;
      using (var reader = new StreamReader(ms))
        return reader.ReadToEnd();
    }
  }

  public string GenerateString(params string[] parameters)
  {
    SetReplacements(parameters);
    return GenerateString();
  }

  public void GenerateString(StreamWriter writer, params string[] parameters)
  {
    SetReplacements(parameters);
    GenerateString(writer);
  }
}

Answer 9

StringBuilder sb = new StringBuilder("Hello string");
sb.Replace("string", String.Empty);
Console.WriteLine(sb);  

StringBuilder , una cadena mutable.