String.Replace .NET Framework的内存效率和性能

Question

String.Replace .NET Framework的内存效率和性能

 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);

Run Code Online (Sandbox Code Playgroud)

我继承了一些与上面的代码片段相同的代码.它需要一个巨大的字符串,并从大字符串中替换(删除)常量较小的字符串.

我相信这是一个非常耗费内存的过程,因为每个替换都会在内存中分配新的大型不可变字符串,等待通过GC死亡.

1.更换这些值的最快方法是什么,忽略内存问题？

2.实现相同结果的最有效的内存方式是什么？

我希望这些是相同的答案!

在这些目标之间适合某些地方的实用解决方案也值得赞赏.

假设:

所有替换都是不变的并且事先已知
底层字符确实包含一些unicode [non-ascii]字符

Answer 1

Jon*_*eet 23

.NET字符串中的所有字符都是"unicode chars".你的意思是他们不是ascii吗？这不应该有任何可能性 - 除非你遇到组合问题,例如当你试图取代"急性"时不会被替换为"e +急性重音".

您可以尝试使用正则表达式Regex.Replace,或StringBuilder.Replace.这里的示例代码与两者做同样的事情:

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);
    }
}

Run Code Online (Sandbox Code Playgroud)

我不想猜哪个更有效 - 你必须根据你的具体应用进行基准测试.正则表达式方式可以在一次传递中完成所有操作,但与StringBuilder中的许多替换相比,该传递将相对CPU密集.

@Ahmed:我宁愿相信实际的基准而不仅仅是收到的智慧 - 我怀疑它依赖于数据*. (4认同)
@Atømix:不,编译器不会将""更改为String.Empty.他们*是*不同的东西......我碰巧发现""更具可读性. (2认同)

Answer 2

Joh*_*ren 13

如果你想要非常快,我的意思是非常快,你必须超越StringBuilder并编写优秀的代码.

你的计算机不喜欢做的一件事就是分支,如果你可以编写一个在固定数组(char*)上运行的替换方法而且没有分支你就有很好的性能.

你要做的是替换操作将搜索一系列字符,如果找到任何这样的子字符串,它将替换它.实际上,您将复制字符串,并在执行此操作时,执行查找和替换.

您将依赖这些函数来选择一些缓冲区的索引来读/写.目标是预先形成替换方法,这样当没有什么必须改变时,你写垃圾而不是分支.

您应该能够在没有单个if语句的情况下完成此操作并记住使用不安全的代码.否则,您将为每个元素访问支付索引检查费用.

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

Run Code Online (Sandbox Code Playgroud)

我在C#中编写了这样的代码以获得乐趣,并且看到了显着的性能改进,几乎300%的速度用于查找和替换.虽然.NET BCL(基类库)执行得很好,但它充满了分支结构和异常处理,如果你使用内置的东西,这将减慢代码的速度.此外,JIT编译器不会执行完美声音的这些优化,您必须将代码作为发布版本运行,而无需附加任何调试器,以便能够观察到大量的性能提升.

我可以为您提供更完整的代码,但这是一项大量的工作.但是,我可以向您保证,它将比目前为止提出的任何其他建议更快.

如果您仔细查看实际的实现，可以做一些事情，但是很遗憾，我没有CLR源的访问权限。我敢打赌，这很好，但并不特别。通过不确定基于后缀数组的实现，可以更快地解决大字符串中的替换问题，尽管不确定是否存在引爆点，但即使是最琐碎的线性搜索算法，也可以通过利用托管中没有的新硬件和内在函数来更快地完成码。您可以付出很多努力并使其更快，但是在某些时候很难捍卫您花费在它上面的时间。 (2认同)

Answer 3

Rob*_*ear 6

1.更换这些值的最快方法是什么,忽略内存问题？

最快的方法是构建一个特定于您的用例的自定义组件.从.NET 4.6开始,BCL中没有为多个字符串替换设计的类.

如果你需要快速的BCL,StringBuilder是最快的BCL组件,用于简单的字符串替换.源代码可以在这里找到:它替换单个字符串非常有效.如果你真的需要正则表达式的模式匹配能力,只能使用正则表达式.即使在编译时,它也会变得更慢,更麻烦.

2.实现相同结果的最有效的内存方式是什么？

最节省内存的方法是执行从源到目标的过滤流复制(如下所述).内存消耗将仅限于您的缓冲区,但这会占用更多CPU; 根据经验,您将为内存消耗交换CPU性能.

技术细节

字符串替换很棘手.即使在可变内存空间(例如使用StringBuilder)中执行字符串替换,也很昂贵.如果替换字符串的长度与原始字符串的长度不同,那么您将重新定位替换字符串后面的每个字符,以使整个字符串保持连续.这导致大量内存写入,即使在StringBuilder的情况下,也会导致您在每次调用Replace时重写内存中的大部分字符串.

那么进行字符串替换的最快方法是什么？使用单遍写入新字符串:不要让代码返回并且必须重写任何内容.写入比读取更昂贵.您将不得不自己编写代码以获得最佳效果.

高内存解决方案

我写的类根据模板生成字符串.我在一个模板中放置了令牌($ ReplaceMe $),该模板标记了我想在以后插入字符串的位置.我在XmlWriter过于繁琐的情况下使用它,因为XML很大程度上是静态的和重复的,我需要生成大型XML(或JSON)数据流.

该类通过将模板切片成部分并将每个部分放入编号字典中来工作.参数也是枚举的.将部件和参数插入新字符串的顺序放入整数数组中.生成新字符串时,将从字典中选取部件和参数,并用于创建新字符串.

它既没有完全优化也没有防弹,但它非常适合从模板生成非常大的数据流.

低内存解决方案

您需要从源字符串中读取小块到缓冲区,使用优化的搜索算法搜索缓冲区,然后将新字符串写入目标流/字符串.这里有很多潜在的警告,但它可以提高内存效率,并且是动态且无法缓存的源数据的更好解决方案,例如整页翻译或太大而无法合理缓存的源数据.我没有这个方便的样本解决方案.

示例代码

期望的结果

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

Run Code Online (Sandbox Code Playgroud)

模板

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

Run Code Online (Sandbox Code Playgroud)

测试用例

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]);
  }
}

Run Code Online (Sandbox Code Playgroud)

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);
  }
}

Run Code Online (Sandbox Code Playgroud)

Answer 4

Mar*_*son 6

我已经在这个线程中结束了几次，在阅读了之前的答案后，我还没有完全相信，因为一些基准测试是用秒表完成的，它可能会给出某种指示，但感觉不太好。

我的用例是，我有一个可能很大的字符串，即网站的 HTML 输出。我需要用值替换该字符串中的一些占位符（大约 10 个，最多 20 个）。

我创建了一个 Benchmark.NET 测试来获取一些可靠的数据，以下是我的发现：

总而言之：

如果性能/内存是一个问题，请不要使用 String.Replace 。

Regex.Replace 速度最快，但使用的内存比 StringBuilder.Replace 稍多。如果您打算重用相同的模式，则编译正则表达式是最快的，对于使用次数较少的情况，创建非编译正则表达式实例的成本更低。

如果您只关心内存消耗并且可以接受较慢的执行速度，请使用 StringBuilder.Replace

测试结果：

| Method | ItemsToReplace | Mean | Error | StdDev | Gen 0 | Gen 1 | Gen 2 | Allocated | |---------------------- |--------------- |-----------:|----------:|----------:|--------:|-------:|------:|----------:| | StringReplace | 3 | 21.493 us | 0.1182 us | 0.1105 us | 3.6926 | 0.0305 | - | 18.96 KB | | StringBuilderReplace | 3 | 35.383 us | 0.1341 us | 0.1119 us | 2.5024 | - | - | 13.03 KB | | RegExReplace | 3 | 19.620 us | 0.1252 us | 0.1045 us | 3.4485 | 0.0305 | - | 17.75 KB | | RegExReplace_Compiled | 3 | 4.573 us | 0.0318 us | 0.0282 us | 2.7084 | 0.0610 | - | 13.91 KB | | StringReplace | 10 | 74.273 us | 0.7900 us | 0.7390 us | 12.2070 | 0.1221 | - | 62.75 KB | | StringBuilderReplace | 10 | 115.322 us | 0.5820 us | 0.5444 us | 2.6855 | - | - | 13.84 KB | | RegExReplace | 10 | 24.121 us | 0.1130 us | 0.1002 us | 4.4250 | 0.0916 | - | 22.75 KB | | RegExReplace_Compiled | 10 | 8.601 us | 0.0298 us | 0.0279 us | 3.6774 | 0.1221 | - | 18.92 KB | | StringReplace | 20 | 150.193 us | 1.4508 us | 1.3571 us | 24.6582 | 0.2441 | - | 126.89 KB | | StringBuilderReplace | 20 | 233.984 us | 1.1707 us | 1.0951 us | 2.9297 | - | - | 15.3 KB | | RegExReplace | 20 | 28.699 us | 0.1179 us | 0.1045 us | 4.8218 | 0.0916 | - | 24.79 KB | | RegExReplace_Compiled | 20 | 12.672 us | 0.0599 us | 0.0560 us | 4.0894 | 0.1221 | - | 20.95 KB |
Run Code Online (Sandbox Code Playgroud)
所以我的结论是：

Regex.Replace 是快速执行和合理内存使用的方法。使用编译的共享实例来加速。

StringBuilder 的内存占用量最低，但比 Regex.Replace 慢很多。只有当内存是唯一重要的事情时我才会使用它。

基准测试的代码如下所示：

| Method | ItemsToReplace | Mean | Error | StdDev | Gen 0 | Gen 1 | Gen 2 | Allocated | |---------------------- |--------------- |-----------:|----------:|----------:|--------:|-------:|------:|----------:| | StringReplace | 3 | 21.493 us | 0.1182 us | 0.1105 us | 3.6926 | 0.0305 | - | 18.96 KB | | StringBuilderReplace | 3 | 35.383 us | 0.1341 us | 0.1119 us | 2.5024 | - | - | 13.03 KB | | RegExReplace | 3 | 19.620 us | 0.1252 us | 0.1045 us | 3.4485 | 0.0305 | - | 17.75 KB | | RegExReplace_Compiled | 3 | 4.573 us | 0.0318 us | 0.0282 us | 2.7084 | 0.0610 | - | 13.91 KB | | StringReplace | 10 | 74.273 us | 0.7900 us | 0.7390 us | 12.2070 | 0.1221 | - | 62.75 KB | | StringBuilderReplace | 10 | 115.322 us | 0.5820 us | 0.5444 us | 2.6855 | - | - | 13.84 KB | | RegExReplace | 10 | 24.121 us | 0.1130 us | 0.1002 us | 4.4250 | 0.0916 | - | 22.75 KB | | RegExReplace_Compiled | 10 | 8.601 us | 0.0298 us | 0.0279 us | 3.6774 | 0.1221 | - | 18.92 KB | | StringReplace | 20 | 150.193 us | 1.4508 us | 1.3571 us | 24.6582 | 0.2441 | - | 126.89 KB | | StringBuilderReplace | 20 | 233.984 us | 1.1707 us | 1.0951 us | 2.9297 | - | - | 15.3 KB | | RegExReplace | 20 | 28.699 us | 0.1179 us | 0.1045 us | 4.8218 | 0.0916 | - | 24.79 KB | | RegExReplace_Compiled | 20 | 12.672 us | 0.0599 us | 0.0560 us | 4.0894 | 0.1221 | - | 20.95 KB |
Run Code Online (Sandbox Code Playgroud)

归档时间：	16 年，8 月前
查看次数：	36216 次
最近记录：	6 年，12 月前