C#如何高效处理整数分拆排列生成的超大规模IEnumerable集合

你需求的带全排列的加数拆分属于数论中的有序整数分拆（Composition），长度为N的有序分拆总数量为2^(N-1)：

• N=20时对应524288条，和你观测的结果一致
• N=50时对应562949953421312条，哪怕每条处理只需要1纳秒，也需要近7天才能跑完
• N=365时的分拆数量远大于可观测宇宙的原子总数，不可能通过穷举完成计算，建议先确认业务需求是否存在不需要穷举的数学优化空间

以下优化可以将现有逻辑的性能提升至少1~2个数量级，且保留分拆生成和业务计算的解耦，不会出现你担心的不优雅问题： #

1. 预计算公共值 #

提前把SomeEquation的返回值缓存到数组，避免每次遍历都重复调用函数：

// 初始化时只计算一次
float[] preCalc = new float[N + 1];
for (int i = 1; i <= N; i++)
{
    preCalc[i] = SomeEquation(i);
}

如果需要统计分拆数量，直接计算1 << (N - 1)（N小于31时）即可，不需要遍历迭代器调用Count()。 #

2. 消除数组分配开销 #

你现有SplitAddends方法的最大性能损耗来自每次递归都分配新的int数组，伴随大量GC开销。可以改用栈分配缓冲区+回溯的方式生成序列，完全无堆分配：

void ProcessCompositions(int n, Action<ReadOnlySpan<int>> processor)
{
    // 缓冲区直接分配在栈上，无GC开销
    Span<int> buffer = stackalloc int[n];
    Recurse(n, 0);

    void Recurse(int remaining, int position)
    {
        if (remaining == 0)
        {
            // 对外暴露当前有效序列的视图，不产生拷贝
            processor(buffer[..position]);
            return;
        }
        for (int i = 1; i <= remaining; i++)
        {
            buffer[position] = i;
            Recurse(remaining - i, position + 1);
        }
    }
}

调用时只需要传入业务处理逻辑即可，完全解耦：

ProcessCompositions(N, variant =>
{
    float someResult = 0f;
    foreach (var item in variant)
    {
        someResult += preCalc[item];
    }
    SendToCompare(someResult);
});

3. 进一步消除序列遍历开销 #

如果你的业务逻辑只是累加序列元素的预计算值，可以在递归时直接传递当前累加值，连序列遍历的开销都可以完全省掉：

void ProcessCompositionSums(int n, float[] preCalc, Action<float> resultHandler)
{
    Recurse(n, 0f);

    void Recurse(int remaining, float currentSum)
    {
        if (remaining == 0)
        {
            resultHandler(currentSum);
            return;
        }
        for (int i = 1; i <= remaining; i++)
        {
            Recurse(remaining - i, currentSum + preCalc[i]);
        }
    }
}

调用方式：

ProcessCompositionSums(N, preCalc, SendToCompare);

4. 正确的并行优化 #

如果需要并行处理，不要直接并行遍历迭代器，按分拆的首元素拆分任务交给线程池即可：

void ParallelProcessCompositionSums(int n, float[] preCalc, Action<float> resultHandler)
{
    Parallel.For(1, n + 1, i =>
    {
        ProcessCompositionSums(n - i, preCalc, sum =>
        {
            resultHandler(sum + preCalc[i]);
        });
    });
}

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