c# - 使用 SelectMany、GroupBy 和 First 的 LINQ 性能

Question

今天我试图解决https://projecteuler.net/problem=5使用 LINQ。

这在我的机器上工作正常并在 2 秒内执行，但有点冗长:

Enumerable.Range(1, 1000000000)
    .Where(i => i % 2 == 0
        && i % 3 == 0
        && i % 4 == 0
        && i % 5 == 0
        && i % 6 == 0
        && i % 7 == 0
        && i % 8 == 0
        && i % 9 == 0
        && i % 10 == 0
        && i % 11 == 0
        && i % 12 == 0
        && i % 13 == 0
        && i % 14 == 0
        && i % 15 == 0
        && i % 16 == 0
        && i % 17 == 0
        && i % 18 == 0
        && i % 19 == 0
        && i % 20 == 0
    )
    .First()

所以我也尝试将 2-19 范围放入一个 Enumerable 中并像这样进行交叉连接

Enumerable.Range(1, 1000000000)
    .SelectMany(n =>
        Enumerable.Range(2, 19)
            .Select(d => (n, d))
    )
    .GroupBy(x => x.n)
    .Where(g => g.All(y => y.n % y.d == 0))
    .First()
    .Key

第二个解决方案的问题是它分配过多，在 x86 LINQPad 中崩溃并出现 OutOfMemoryException，并且在我手动杀死它之前在 x64 LINQPad 版本中消耗了大量内存。

我的问题是为什么？ 是否有可以避免该问题的 LINQ 查询？

CLR 堆分配分析器插件告诉我内部正在进行堆分配

.Select(d => (n, d))

由于捕获了“n”。 所以我认为这是 OutOfMemoryException 的原因，但是...... 因为我使用 First() 而没有具体化中间的查询，所以我认为这应该不是问题，因为 linq 会具体化该组并再次丢弃它，因为它在释放内存时不满足条件。 selectmany 或 groupby 是否发生了一些奇怪的事情，迫使所有数据首先被具体化，或者我的心智模型在这里是错误的？

Answer 1

如果你试过下面的代码，也会出现同样的问题:

Enumerable.Range(1, 1000000000)
    .GroupBy(x => x)
    .First();

这意味着所有组都将在查询执行期间具体化，这就是抛出 OutOfMemoryException 的原因。

要解决这个问题，可以使用@haim770在评论区提到的如下LINQ代码:

Enumerable
    .Range(1, 1000000000)
    .First(i => Enumerable
        .Range(2, 19)
        .All(j => i % j == 0))

为了进一步优化，我找到了更好的解决方案。很抱歉没有使用 LINQ，但它的优化程度更高，也许有一种方法可以使用 LINQ 来实现它。

与其遍历大量数字并检查每个数字，不如直接构建所需的答案。

所需的输出是一个数字x，它可以被所有数字1..n 整除而没有余数。因此，它是 1..n 范围内数字的所有质因数的倍数。通过取最少的这些质因数，我们可以得到最小的数 x。

例如，如果 n = 10 那么:

i = 2: prime factors of 2 are [2] -> neededPrimes = [2]
i = 3: prime factors of 3 are [3] -> neededPrimes = [2, 3]
i = 4: prime factors of 4 are [2, 2] -> neededPrimes = [2, 2, 3] // we add just one 2 because the other already exists in neededPrimes
i = 5: prime factors of 5 are [5] -> neededPrimes = [2, 2, 3, 5]
i = 6: prime factors of 6 are [2, 3] -> neededPrimes = [2, 2, 3, 5] // we add nothing because [2, 3] are already in neededPrimes
i = 7: prime factors of 7 are [7] -> neededPrimes = [2, 2, 3, 5, 7]
i = 8: prime factors of 8 are [2, 2, 2] -> neededPrimes = [2, 2, 2, 3, 5, 7] // we add one 2 because the other 2's already exist in neededPrimes
i = 9: prime factors of 9 are [3, 3] -> neededPrimes = [2, 2, 2, 3, 3, 5, 7]
i = 10: prime factors of 10 are [2, 5] -> neededPrimes = [2, 2, 2, 3, 3, 5, 7]

x = 2 * 2 * 2 * 3 * 3 * 5 * 7 = 2520

这是一段代码，我希望它很清楚:

public static void Main(string[] args)
{
    // The number to find its smallest multiple
    var n = 20;
    // A list that contains all primes that are founded across the calculation
    var calculatedPrimes = new List<int>();
    // Start through the numbers that x (the output number) should be divisible by
    for (var i = 2; i <= n; i++)
    {
        // Get primes of i
        var primes = GetPrimeFactors(i);
        // Loop through primes of i and add to "calculatedPrimes" the ones that are not 
        // in "calculatedPrimes"
        primes.ForEach(prime =>
        {
            if (!calculatedPrimes.Contains(prime) ||
                calculatedPrimes.Count(p => p == prime) < primes.Count(p => p == prime))
            {
                calculatedPrimes.Add(prime);
            }
        });
    }

    // The output number should be the multiple of all primes in "calculatedPrimes" list
    var x = calculatedPrimes.Aggregate(1, (res, p) => res * p);
    Console.WriteLine(x);

    Console.ReadLine();
}

// A function to get prime factors of a given number n
// (example: if n = 12 then this will return [2, 2, 3])
private static List<int> GetPrimeFactors(int n)
{
    var res = new List<int>();
    while (n % 2 == 0)
    {
        res.Add(2);
        n /= 2;
    }

    for (var i = 3; i <= Math.Sqrt(n); i += 2)
    { 
        while (n % i == 0)
        {
            res.Add(i);
            n /= i;
        }
    }

    if (n > 2)
        res.Add(n);
    return res;
}