C# 如何产生返回 SelectMany？

Question

假设我有以下通用组合生成器静态方法:

public static IEnumerable<IEnumerable<T>> GetAllPossibleCombos<T>(
    IEnumerable<IEnumerable<T>> items)
{
    IEnumerable<IEnumerable<T>> combos = new[] {new T[0]};

    foreach (var inner in items)
        combos = combos.SelectMany(c => inner, (c, i) => c.Append(i));

     return combos;
}

也许我没有正确理解这一点，但这不是在 RAM 中构建了整个组合列表吗？如果有大量项目，该方法可能会导致计算机内存不足。

有没有办法重写方法以在每个组合上使用 yield return，而不是返回整个组合集？

Answer 1

你的问题中有一些误解，这很棒，因为现在你有机会了解事实而不是神话。

---

首先，您正在实现的方法通常称为 CartesianProduct , 不是 GetAllPossibleCombos , 所以考虑重命名它。

---

Perhaps I am not understanding this correctly

你没有理解正确。

doesn't this build the entire combos list in RAM?

没有。 查询构建器构建查询，而不是执行查询的结果。当您执行 SelectMany 时，你得到的是一个对象，以后会做选择。您不会获得该选择的结果。

If there are a large number of items the method might cause the computer to run out of RAM.

今天是停止将内存和 RAM 视为同一事物的好日子。当进程用完内存时，它不会用完 RAM。它用完了地址空间，这不是 RAM。考虑内存的更好方法是:内存是磁盘上的页面文件，而 RAM 是使页面文件更快的特殊硬件。当您用完 RAM 时，您的机器可能会变得慢得无法接受，但您不会用完内存，直到您用完地址空间。请记住，进程内存是虚拟化的。

现在，可能会出现执行此代码效率低下的情况，因为枚举查询用完了堆栈。并且可能存在执行效率低下的情况，因为您将 n 项向上移动到 n 深的堆栈中。我建议您对您的代码进行更深入的分析，看看是否属于这种情况，然后再报告。

---

Is there a way to re-write the method to use a yield return on each combo, instead of returning the entire combos set?

SelectMany实现为 yield return在foreach循环，因此您已经将其实现为 yield return在每个组合上；你刚刚隐藏了 yield return在对 SelectMany 的调用中.

即SelectMany<A, B, C>(IE<A> items, Func<A, IE<B>> f, Func<A, B, C> g)实现方式如下:

foreach(A a in items)
  foreach(B b in f(a))
    yield return g(a, b);

所以你已经在 yield return 中完成了.

如果你想写一个直接做yield return的方法那有点难；最简单的方法是在每个子序列上形成一个枚举器数组，然后从每个 Current 生成一个向量的普查员，yield return向量，然后将正确的迭代器前进一步。继续这样做，直到不再有正确的迭代器可以推进。

正如您可能从该描述中看出的那样，簿记变得一团糟。这是可行的，但编写起来不是很愉快。试一试吧!该解决方案的好处在于，您可以保证获得良好的性能，因为您不会消耗任何堆栈。

更新:这个相关问题发布了一个执行迭代算法的答案，但我没有检查它是否正确。 https://stackoverflow.com/a/57683769/88656

---

最后，我鼓励您将您的实现与我的进行比较:

https://ericlippert.com/2010/06/28/computing-a-cartesian-product-with-linq/

我的实现是否与您的有任何根本的不同，或者我们做的是同一件事，只是语法略有不同？考虑一下。

此外，我还鼓励您阅读 Ian Griffiths 出色的六部分系列文章，该系列文章分析了该函数的各种实现:

http://www.interact-sw.co.uk/iangblog/2010/07/28/linq-cartesian-1