如何优化这段代码?(也许是LINQ?)

本文关键字：代码 LINQ 也许 何优化 优化 段代码 | 更新日期: 2023-09-27 17:50:48

我有这样的代码:

ArrayList arrayA = new ArrayList();
ArrayList arrayB = new ArrayList();
ArrayList arrayC = new ArrayList();
ArrayList arrayD = new ArrayList();
ArrayList arrayE = new ArrayList();
ArrayList arrayF = new ArrayList();
ArrayList arrayG = new ArrayList();
ArrayList arrayH = new ArrayList();
ArrayList arrayI = new ArrayList();
ArrayList arrayJ = new ArrayList();
int n = 0;
for (decimal a = 0.1m; a <= 100m; a += 0.1m)
{
    for (decimal b = 100m - a; b > 0m; b -= 0.1m)
    {
        for (decimal c = 100m - b; c > 0m; c -= 0.1m)
        {
            for (decimal d = 100m - c; d > 0m; d -= 0.1m)
            {
                for (decimal e = 100m - d; e > 0m; e -= 0.1m)
                {
                    for (decimal f = 100m - e; f > 0m; f -= 0.1m)
                    {
                        for (decimal g = 100m - f; g > 0m; g -= 0.1m)
                        {
                            for (decimal h = 100m - g; h > 0m; h -= 0.1m)
                            {
                                for (decimal i = 100m - h; i > 0m; i -= 0.1m)
                                {
                                    for (decimal j = 100m - i; j > 0m; j -= 0.1m)
                                    {
                                        if ((a + b + c + d + e + f + g + h + i + j) == 100)
                                        {
                                            ++n;
                                            arrayA.Add(a);
                                            arrayB.Add(b);
                                            arrayC.Add(c);
                                            arrayD.Add(d);
                                            arrayE.Add(e);
                                            arrayF.Add(f);
                                            arrayG.Add(g);
                                            arrayH.Add(h);
                                            arrayI.Add(i);
                                            arrayJ.Add(j);
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}

有什么想法如何优化这个吗?这将花费很长时间执行。

基本上需要的是知道0.1到100之间的10个数字的组合个数，它们的和正好是100。(我需要知道组合的数量和组合本身)

提前感谢

如何优化这段代码?(也许是LINQ?)

我不认为这个问题有一个直接的解决方案，特别是对于这种类型的数字。但这里有一个非常一般的想法，可以帮助您开发自己的算法:

  1. 了解关于Gosper的Hack。它可以生成复杂度为0 (n)的组合。
  2. 您将意识到需要生成C(1000,10)个组合，这是不能直接使用原始数据类型的。为了克服这个问题，你可以实现你自己的类，它可以用必要的操作来表示大的位序列，比如添加和移动等(或者你可以在你的标准库中找到一个类似的类并扩展它。)

我知道这不是一项容易的任务，我不想自己实现它。但是它会给你一个O(n)的时间复杂度，你只需要在线性时间内迭代这些组合，用那个位序列在0.1到100之间选择数字，用步骤0.1检查它们的和是否为100。并将位序列添加到最后的ArrayList中。

编辑Ronan Thibaudau的警告:我很抱歉我直接跳到Java，但我认为你可以在你喜欢的语言/框架中找到相应的方法。

又一个编辑:现在这篇文章是语言独立的。想法完全一样…我要说的是;如果您正在研究具有大型组合的此类问题，那么这种想法可能会给您带来O(n)的时间复杂度和O(n)的内存需求。这实际上保证了它将在可行的时间内运行，在给定足够大的n的情况下消耗可行的内存量。

自我编辑:我还在想，必须更正一下。(我保留了一些错误的算法分析)

Gosper's Hack绝对会给你O(n)时间复杂度来生成组合，这对于具有可接受的优化实现至关重要。但是，由于您必须创建自己的类来表示位序列，因此您必须实现自己的移位器，加法器，手和诸如此类的东西(即。您不能直接使用您的硬件进行这些操作)。为此，你需要另一个n-loop。这可能会使你的算法复杂度为O(n2)

它肯定不如O(n)好，但仍然应该满足您的执行时间需求。

如果你真的想优化提议的算法，我会从省略不必要的循环开始，如果总和>= 100，继续是没有意义的，例如:

for (decimal a = 0.1m; a <= 100m; a += 0.1m)
{
    for (decimal b = 100m - a; b > 0m; b -= 0.1m)
    {
        if (a + b >= 100m)
             continue;
             for (decimal c = 100m - b; c > 0m; c -= 0.1m)
             {
                 if (a + b + c >= 100m)
                     continue;
                 ...

无论如何，你永远无法存储所有的组合。例如，如果你只有三个数字，输出将由1000^2个结果组成。第一个数字你可以任意选择(0.1…100，所以你有1000个选择)，第二个也是如此，例如，我选择0.5和42 -第三个我固定了，57.5 -所以它是1000 * 1000 * 1好结果。现在扩展到10个数字。

我认为这是使用LINQ完成此操作的最佳方法:

var n = 1000;
var query =
    from a in Enumerable.Range(1, n)
    from b in Enumerable.Range(1, n - a)
    from c in Enumerable.Range(1, n - a - b)
    from d in Enumerable.Range(1, n - a - b - c)
    from e in Enumerable.Range(1, n - a - b - c - d)
    from f in Enumerable.Range(1, n - a - b - c - d - e)
    from g in Enumerable.Range(1, n - a - b - c - d - e - f)
    from h in Enumerable.Range(1, n - a - b - c - d - e - f - g)
    from i in Enumerable.Range(1, n - a - b - c - d - e - f - g - h)
    let j = n - a - b - c - d - e - f - g - h - i
    where j >= 1
    select new { a, b, c, d, e, f, g, h, i, j };

我选择使用int并将数字乘以10，而不是使用decimal与0.1增量。

现在用1000运行这个似乎需要很长时间。

所以我开始用较小的数字运行它，得到了这些结果:

10  1
11  10
12  55
13  220
14  715
15  2002
16  5005
17  11440
18  24310
19  48620
20  92378

那是n &返回的组合数。

结果表明这个级数是C(n - 1, n - 10)。因此，插入n = 1000，我得到2,634,095,604,619,700,000,000个组合。

现在，在我的计算机上，如果我运行n = 30，它需要11.551秒来计算10,015,005个组合。

如果你做数学计算，假设每年有365.25天，那么你得出的数字将需要96,271,110年来计算n = 1000。

就连"深思"在计算42的时候也更快。祝你好运。

这里有一个答案(从1到1000，而不是简单地从0.1到100，简单地将所有项目除以10，得到0.1到100的值)

首先，我们将使用生成器枚举数和惰性操作符来避免内存问题，所有内容都将逐个流式传输到管道中，因此在代码运行时应该修复内存

var kitems = Enumerable.Range(1,1000);
var q = from a in kitems
        from b in kitems
        from c in kitems
        from d in kitems
        from e in kitems
        from f in kitems
        from g in kitems
        from h in kitems
        from i in kitems
        from j in kitems
        where a+b+c+d+e+f+g+h+i+j == 1000
        select new {a,b,c,d,e,f,g,h,i,j};
// Since everything is lazy evaluated, the 10 first results are near immediate (nothing past those is evaluate, this is good for testing, remove the take operator if you want the full dataset)
foreach(var item in q.Take(10))
{
    // Do whatever you want with the result here
}

让我们对整数(1到1000，求和1000)进行推理。设C(K, N)为涉及K个变量的组合个数，共N个

对于单个变量，我们有1种可能性(a=1000)，即C(1,1000)=1。更一般地说，C(1, N)=1.

对于两个变量，我们有999种组合(a=1, b=999到a=999, b=1)，我们看到C(2,1000)= C(1,999) + C(1,998) + C(1,997) +…C(1,1).更一般地说，C(2, N) = N-1.

对于三个变量，我们有C(2,999)种组合，a=1, C(2,998)种组合，a=2…C(2,2)， a=998。根据三角数公式，C(3, N) = N (N-1)/2。

对于四个变量，我们有C(3,999)种组合，a=1, C(3,998)种组合，a=2…C(3,3)， a=997。由四面体数的公式C(4, N)= N (N-1).(N-2)/6.

以此类推(这就是Pascal三角形)，直到:

C (10 N) = N (N - 1),(2)。(N)。(4)。(4)。(N-6)。(N-7)。(N-8)。(N - 9)/9 !

C(10,1000) = 2634095604619702128324000

不可能通过枚举来计算这个天文数字!

相关文章：