C# 序列逐次去头子集应用函数的实现方案咨询

简介 #

假设存在如下序列：

var ls = new[]{10, 20, 30, 40};

需要对以下子集分别应用指定函数：

• 完整序列
• 丢弃第1个头部元素后的序列
• 丢弃前2个头部元素后的序列
• 以此类推...

现有实现方案 #

当前给出的一种实现方式如下：

IEnumerable<U> f_a<T,U>(IEnumerable<T> seq, Func<IEnumerable<T>, U> proc) =>
    Enumerable
        .Range(0, seq.Count())
        .Select(n => seq.Skip(n))
        .Select(proc);

使用示例 #

示例1：拼接各子集元素：

示例2：计算各子集的和：

示例3：计算各子集和同时展示对应序列：

（以上示例均在VS Code的dotnet-interactive环境中生成）

针对三个问题逐一说明如下：

1. .NET是否有内置实现？ #

没有。截至.NET 8，System.Linq命名空间下的内置API没有提供直接生成序列所有后缀子集的封装，现有Skip/Take等方法仅支持单次截取，无法直接实现上述f_a的逻辑。

2. 更优的实现方案 #

现有实现存在三个明显的性能和兼容性问题：

• 对非集合类型的IEnumerable<T>（比如惰性迭代器、数据库查询结果）调用Count()会完整枚举一次源序列，后续每一次Skip(n)又会从头枚举源序列，整体时间复杂度为O(n²)
• 如果传入的是不可重入的只进序列（比如从DbDataReader转换得到的序列），多次枚举会直接抛出异常或返回错误结果
• 枚举过程中如果源序列被修改，Count()和后续Skip拿到的结果会不一致

更稳妥高效的实现可以参考下面的版本，先一次性缓冲源序列，再通过索引切片生成后缀，避免重复枚举开销，同时兼容所有IEnumerable<T>类型：

public static IEnumerable<U> F_A<T, U>(IEnumerable<T> seq, Func<IEnumerable<T>, U> proc)
{
    // 一次性缓冲源序列，解决多次枚举问题
    var buffered = seq.ToList();
    for (int i = 0; i < buffered.Count; i++)
    {
        // 对List<T>用GetRange生成后缀，比Skip效率高一个量级，不需要从头遍历
        yield return proc(buffered.GetRange(i, buffered.Count - i));
    }
}

如果需要支持超大型序列、无法一次性缓冲到内存，可以用链表结构实现惰性枚举的后缀生成，不过实现复杂度更高，且需要注意每个返回的子序列枚举时互不干扰，绝大多数业务场景下上面的缓冲实现已经足够好用。

3. 其他语言的等价实现 #

这个操作在函数式编程领域是非常通用的操作，通常命名为**tails（后缀序列生成）**，很多语言的标准库或主流工具库都有内置实现：

• Haskell：Data.List模块内置tails函数，注意其返回结果最后会包含一个空列表，和上述需求相比只需要去掉最后一个元素即可
• Scala：标准库的List、Iterator等集合类型都内置tails方法，直接返回所有后缀的迭代器
• Python：标准库itertools没有直接提供，但主流第三方工具库more-itertools中包含tails实现
• JavaScript：Ramda、Lodash/fp等主流函数式工具库都提供tails方法
• F#：虽然标准库没有内置，但FSharpx等官方扩展库中提供了Seq.tails实现，自行实现也仅需数行代码。

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