C#：将字符串插入另一个字符串 - 性能问题

Question

我有一个很长的字符串，以及一个索引和值的排序字典。我应该检查字典中的元素并将值插入到字符串中的指定索引。我编写了以下代码，它工作正常，但速度非常慢：

private string restoreText(string text){
  StringBuilder sb = new StringBuilder(text);
  foreach(KeyValuePair<int, string> pair in _tags){
    sb.Insert(pair.Key, pair.Value);
  }
  return sb.ToString();
}

字典可能非常大，包含 500,000 个元素。 我认为导致这个函数变慢的是 Insert() 方法。对于10万个元素的字典，花费了将近5秒。

有没有更有效的方法来编写这个方法？

谢谢，

玛雅

Answer 1

更好的方法是对要插入的项目进行排序，然后将它们一个接一个地附加。

既然您没有对重叠发表评论，也许您首先已经对物品进行了排序？

Answer 2

您的原始代码将根据从 _tags 返回项目的顺序给出不同的结果；我非常怀疑这不是你的意图。

相反，按顺序对标签进行排序，然后按正确的顺序将它们添加到字符串生成器中：

private string restoreText(string text)
{
    StringBuilder sb = new StringBuilder();
    foreach( KeyValuePair<int, string> pair in _tags.OrderBy(t => t.Key))
    {
        sb.Append(pair.Value);
    }

    return sb.ToString();
}

如果您确实想让此操作尽可能快，请预先初始化 StringBuilder 的容量：

    StringBuilder sb = new StringBuilder(_tags.Sum(k => k.Value.Length));

更新

我错过了最初用于初始化StringBuilder的text参数。

为了避免在内存中打乱文本（由 StringBuilder.Insert() 引起），我们希望坚持使用 StringBuilder.Append()。

我们可以通过将原始文本转换为另一个 KeyValuePair 实例序列，将它们与原始列表合并并按顺序处理来实现此目的。

它看起来像这样（注意：临时代码）：

private string restoreText(string text)
{
    var textPairs 
        = text.Select( (c,i) => new KeyValuePair<int,string>(i, (string)c));
    var fullSequence
        = textPairs.Union(_tags).OrderBy(t => t.Key);
    StringBuilder sb = new StringBuilder();
    foreach( KeyValuePair<int, string> pair in fullSequence)
    {
        sb.Append(pair.Value);
    }

    return sb.ToString();
}

注意 - 我对您的上下文做了一大堆假设，所以这可能不太适合您。特别要注意的是，.Union() 将丢弃重复项，尽管有一些简单的解决方法。

Answer 3

如果您设置了索引，以便插入不会更改其他索引，那么我不会得到什么，但正如您的代码所说“是”，我也会这么认为。

你能测试一下这个吗：

private string RestoreText(string text)
{
    var sb = new StringBuilder();
    var totalLen = 0;
    var orgIndex = 0;
    foreach (var pair in _tags.OrderBy(t => t.Key))
    {
        var toAdd = text.Substring(orgIndex, pair.Key - totalLen);
        sb.Append(toAdd);
        orgIndex += toAdd.Length;
        totalLen += toAdd.Length;

        sb.Append(pair.Value);
        totalLen += pair.Value.Length;
    }
    if (orgIndex < text.Length) sb.Append(text.Substring(orgIndex));
    return sb.ToString();
}

它只使用追加，同时与你的原始代码相同

Answer 4

我不知道你的数据怎么样。

但在我的测试中，它运行得很快（564ms）。

        Dictionary<int, string> _tags = new Dictionary<int, string>();
        for (int i = 0; i < 1000000; i++)
        {
            _tags.Add(i, i.ToString().Length + "");
        }

        string text = new String('a' , 50000000);
        Console.WriteLine("****************************************");

        System.Diagnostics.Stopwatch sw = System.Diagnostics.Stopwatch.StartNew();

        StringBuilder sb = new StringBuilder(text);
        foreach (KeyValuePair<int, string> pair in _tags)
        {
            sb.Insert(pair.Key, pair.Value);
        }

        sw.Stop();

        Console.WriteLine("sw:" + sw.ElapsedMilliseconds);
        Console.ReadKey();

如果你可以使用 append() 而不是 insert() ，它只需要 35ms...