C#如何产生returnSelectMany？

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

SelectMany 和其他 Linq 方法 return 和 IEnumerable，仅在枚举集合时才对其进行惰性求值。这可以采用 ToList() 或 ToArray() 调用的形式，或者在 foreach 循环中对其进行迭代。当您在调试器中看到消息警告扩展集合将枚举可枚举项时，这就是它警告您的行为。该集合尚未枚举 - Linq 查询仅建立一个调用链，告诉它如何枚举数据。

因此，您对 RAM 使用情况的担忧不一定准确（取决于起始 IEnumerable 的具体类型）。即使您调用 ToList() 或 ToArray() 并将对其的引用存储在变量中，如果集合元素是引用类型，那么它也不会是副本。

在您的示例中，如果您想懒惰地构建元素集合而不将其存储在单独的集合中（例如 return 列表或数组，这需要额外的复制，yield return 会为您提供便利).我不认为它适用于你正在尝试做的事情，因为 SelectMany 已经有这种行为。

如果您想尝试一下，Linq 可以很容易地使用 Enumerable.Repeat

生成大型列表

// Define a collection with 10000000 items (items not created yet)
var manyItems = Enumerable.Repeat(123, 10000000);

// Enumerate the enumerable via ToList: creates the int 10000000 times
var manyItemsConcrete = manyItems.ToList();

// same deal with reference types
var manyReferenceTypes = Enumerable.Repeate(new object(), 10000000);
var manyReferenceTypesConcrete = manyReferenceTypes.ToList();

// This list already exists in RAM taking up space
var list = new List<object> { new object(), new object() /* ... x10000000 */ }
// This defines a transform on list, but doesn't take up RAM
var enumerable = list.Select(x => x.ToString());

// Now, there are two lists taking up RAM
var newList = enumerable.ToList();

Answer 2

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

首先，您要实现的方法通常称为 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 视为同一事物的好日子。当进程运行内存不足时，它不会运行内存不足。它运行来自 地址 space，它不是 RAM。考虑内存的更好方法是：内存是磁盘上的页面文件，RAM 是使页面文件更快的特殊硬件。当你运行内存不足时，你的机器可能会变得慢得无法接受，但你不会运行内存不足内存直到你运行内存不足地址space。请记住，进程内存已虚拟化。

现在，可能存在执行此代码效率低下的情况，因为枚举查询运行出栈 。并且可能存在执行效率低下的情况，因为您将 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 在 foreach 循环中实现为 yield return，因此您已经在每个组合中将其实现为 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://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

C#如何产生returnSelectMany？

C# how to yield return SelectMany?

c#

linq

combinatorics