如何优化到字符串重写规则程序

Question

我有一个小程序，它不断重写相同的字符串

string a = "aRbFR";
string b = "LFaLb";
string str = "Fa";
for (; n < 50; ++n)
{
    for(Int64 i = 0; i < str.Length; ++i)
    {
        if (i < str.Length && str[(int)i] == 'a')
        {
            str = str.Remove((int)i, 1);
            str = str.Insert((int)i, a);
            i += a.Length;
        }
        if (i < str.Length && str[(int)i] == 'b')
        {
            str = str.Remove((int)i, 1);
            str = str.Insert((int)i, b);
            i += b.Length;
        }
    } 
}

例如： n0 = "Fa"， n1 = "FaRbFR"

， n2 = "FaRbFRRLFaLbFR"

这

是否可以进行多线程，因为我需要按顺序更新相同的变量？我以为我可以让我的str不稳定，但我想不出它将如何正常运行，因为所有线程都需要更新相同的变量。

我怎样才能在有效的时间内运行？这需要很长时间，变量仍然处于相当低的索引n = 17

Answer 1

在考虑线程以提高性能之前，最好优化您的算法。事实证明，这适用于Stack，因为它只是创建一棵树并将其展平。时间复杂度急剧下降。

另请注意，由于这基本上是递归的，并且数据需求呈指数级增长，因此即使是堆栈也会耗尽更高级别的内存。 您可能会对这一切进行磁盘缓冲，因为它是一个Stack。

另一个问题是分配，所以一旦反对一个Stack在这里会有所帮助，因为它的内部增长效率更高，StringBuilder

堆栈版本

public static string StackVersion(int levels, string input)
{
   var stack = new Stack<(int l, char c)>();
   void PushAllReverse(int l, string seq)
   {
      for (var index = seq.Length - 1; index >= 0; index--)
         stack.Push((l, seq[index]));
   }
   PushAllReverse(1, input);
   var sb = new StringBuilder();
   while (stack.Any())
   {
      // pop the next
      var val = stack.Pop();
      // limit the levels
      if (val.l < levels)
         // add to stack if needed
         if (val.c == 'a') PushAllReverse(val.l + 1, a);
         else if (val.c == 'b') PushAllReverse(val.l + 1, b);
         else sb.Append(val.c); // append the char
      else
         // level limit, just append
         if (val.c == 'a') sb.Append(a);
         else if (val.c == 'b') sb.Append(b);
         else sb.Append(val.c);
   }
   return sb.ToString();
}

源语言

public static string OriginalVersion(int levels, string input)
{
   for (int n = 0; n < levels; n++)
   {
      for (var i = 0; i < input.Length; i++)
      {
         if (i < input.Length && input[i] == 'a')
         {
            input = input.Remove(i, 1);
            input = input.Insert(i, a);
            i += a.Length;
         }
         if (i < input.Length && input[i] == 'b')
         {
            input = input.Remove(i, 1);
            input = input.Insert(i, b);
            i += b.Length;
         }
      }
   }
   return input;
}

---

测试计时（迭代）

Stack : (5) 00:00:00.0000111
Orig  : (5) 00:00:00.0000105
Stack : (6) 00:00:00.0000228
Orig  : (6) 00:00:00.0000318
Stack : (7) 00:00:00.0000483
Orig  : (7) 00:00:00.0001065
Stack : (8) 00:00:00.0000621
Orig  : (8) 00:00:00.0003524
Stack : (9) 00:00:00.0001143
Orig  : (9) 00:00:00.0014589
Stack : (10) 00:00:00.0002284
Orig  : (10) 00:00:00.0022475
Stack : (11) 00:00:00.0003179
Orig  : (11) 00:00:00.0092901
Stack : (12) 00:00:00.0006805
Orig  : (12) 00:00:00.0222648
Stack : (13) 00:00:00.0013283
Orig  : (13) 00:00:00.0920365
Stack : (14) 00:00:00.0036728
Orig  : (14) 00:00:00.4287529
Stack : (15) 00:00:00.0056583
Orig  : (15) 00:00:01.5850379

---

示例结果 5 次迭代（因为我最初弄错了，所以我最好把结果）

叠

FaRbFRRLFaLbFRRLFaRbFRLLFaLbFRRLFaRbFRRLFaLbFRLLFaRbFRLLFaLbFRRLFaRbFRRLFaLbFRRLFaRbFRLLFaLbFRLLFaRbFRRLFaLbFRLLFaRbFRLLFaLbFR

源语言

FaRbFRRLFaLbFRRLFaRbFRLLFaLbFRRLFaRbFRRLFaLbFRLLFaRbFRLLFaLbFRRLFaRbFRRLFaLbFRRLFaRbFRLLFaLbFRLLFaRbFRRLFaLbFRLLFaRbFRLLFaLbFR

Answer 2

TheGeneral是对的，它只是在穿越一棵树。你用堆栈来做到这一点，但不是显式堆栈，我的第一个选择工具是隐式堆栈，也就是递归。

protected void makeA(int level, StringBuilder sb)
{
    if (level == 0)
    {
        sb.Append('a');
    }
    else
    {
        makeA(level - 1, sb);
        sb.Append("R");
        makeB(level - 1, sb);
        sb.Append("FR");
    }
}
protected void makeB(int level, StringBuilder sb)
{
    if (level == 0)
    {
        sb.Append('b');
    }
    else
    {
        sb.Append("LF");
        makeA(level - 1, sb);
        sb.Append("L");
        makeB(level - 1, sb);
    }
}
protected string makeString(int level)
{
    StringBuilder sb = new StringBuilder();
    sb.Append("F");
    makeA(level, sb);
    return sb.ToString();
}

代码更简单，也比通用版本快五倍左右。但这并不重要。50 次迭代的字符串太大了。这两个计数相等：

double c1 = makeString(i).Count(c => c == 'a' || c == 'b');
double c2 = Math.Pow(2, i);

而 2^50 = 1125899906842624，即仅这两个字符（1 个字符 si 2 字节）的 2.2PB。