Как оптимизировать программу с правилами перезаписи строк

Прежде чем рассматривать потоковую передачу чего-либо для повышения производительности, лучше всего усовершенствовать свой алгоритм. Оказывается, это подходит для 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

Генерал прав, он просто пересекает дерево. Вы делаете это с помощью стека, но я предпочитаю не явный стек, а неявный стек, также известный как рекурсия.

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

Код более простой и примерно в пять раз быстрее, чем версия TheGeneral. Но это не имеет особого значения. Строка для 50 итераций была бы слишком большой. Эти два значения равны:

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

И 2 ^ 50 = 1125899906842624, то есть 2,2 ПБ только для этих двух символов (1 символ si 2 байта).