C#迭代生成超长字符串触发OutOfMemory异常如何解决

你遇到的OOM问题核心原因是直接生成完整迭代后的字符串，而迭代后的字符串长度是指数级增长的，哪怕C只有几十次，长度就会远超内存上限，更不用说10亿次的迭代需求。正确的思路是不生成完整字符串，按需推算目标区间的每一位字符，性能和内存占用都可以控制在极低水平。 #

具体原理 #

1. 先明确迭代的长度规律 #

我们可以先预计算每轮迭代后的字符串长度（用long类型避免溢出，只要长度超过结束索引E就停止计算，不需要算到更大的数值）：

• 记初始A的长度为lenA，即第0轮迭代的长度len[0] = lenA
• 先预处理基础字符串B：统计其中占位符（这里是%）的数量pCount，以及非占位符的总长度fixLen = B.Length - pCount
• 第k轮迭代的长度公式为：len[k] = pCount * len[k-1] + fixLen
  因为指数级增长的特性，哪怕pCount=2，最多30次迭代长度就会超过1e9，就算C是10亿，实际有效计算的轮次最多也就几十次。

2. 倒推目标位置的字符 #

我们只需要求第C轮字符串中[D-1, E-1]区间的字符（因为用户输入的D、E是1开头的索引），对每个目标位置pos，可以从第C轮倒推到第0轮找到对应的字符：
第k轮的字符串结构是：把B中的每一个%替换为第k-1轮的完整字符串，其余固定字符保留。我们遍历B的每个字符：

• 如果当前字符是普通字符：如果pos == 0，直接返回该字符；否则pos -= 1，继续遍历下一个字符
• 如果当前字符是占位符%：对应的是长度为len[k-1]的第k-1轮字符串，如果pos < len[k-1]，说明目标字符在这个替换串里，问题转化为求第k-1轮的pos位置的字符；否则pos -= len[k-1]，继续遍历下一个字符
  倒推到第0轮时，直接返回初始A的pos位置的字符即可。

实现代码示例 #

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        // 读取输入参数
        string A = Console.ReadLine().Trim();
        string B = Console.ReadLine().Trim();
        int C = int.Parse(Console.ReadLine().Trim());
        int D = int.Parse(Console.ReadLine().Trim());
        int E = int.Parse(Console.ReadLine().Trim());
        int needLen = E - D + 1;
        const char fillChar = '-'; // 超出长度时的填充字符
        
        // 预处理B，统计占位符数量，同时把B存为字符数组方便遍历
        char[] bChars = B.ToCharArray();
        int pCount = bChars.Count(c => c == '%');
        
        // 预计算各轮长度，直到长度>=E或者达到C轮
        List<long> lenList = new List<long> { A.Length };
        for (int i = 1; i <= C; i++)
        {
            long nextLen = pCount * lenList.Last() + (bChars.Length - pCount);
            lenList.Add(nextLen);
            if (nextLen >= E) break; // 超过最大需要的位置就不用算了
        }
        
        // 逐个生成目标区间的字符
        char[] result = new char[needLen];
        long finalLen = lenList.Count > C ? lenList[C] : lenList.Last();
        for (int i = 0; i < needLen; i++)
        {
            long pos = D - 1 + i;
            if (pos >= finalLen)
            {
                result[i] = fillChar;
                continue;
            }
            // 倒推找当前pos的字符
            int currentRound = Math.Min(C, lenList.Count - 1);
            long currentPos = pos;
            while (currentRound > 0)
            {
                long prevLen = lenList[currentRound - 1];
                foreach (char c in bChars)
                {
                    if (c != '%')
                    {
                        if (currentPos == 0)
                        {
                            result[i] = c;
                            goto endFind; // 找到字符，跳出所有循环
                        }
                        currentPos--;
                    }
                    else
                    {
                        if (currentPos < prevLen)
                        {
                            currentRound--;
                            break; // 进入上一轮查找
                        }
                        currentPos -= prevLen;
                    }
                }
            }
            // 到第0轮，直接取A的字符
            result[i] = A[(int)currentPos];
            endFind: ;
        }
        
        Console.WriteLine(new string(result));
    }
}

优势说明 #

• 内存占用极低：不需要存储迭代后的完整字符串，最多只需要存储长度数组（最多几十项）和目标区间的字符数组
• 性能足够：每个目标字符的推算次数最多几十次，哪怕目标区间长度是1e4，总计算量也只有几十万次，完全可以在毫秒级完成
• 支持10亿次迭代：因为长度增长是指数级的，实际有效迭代次数最多几十次，完全不受C的上限限制

内容的提问来源于stack exchange，提问作者Matt