可能的优化在我的代码

本文关键字:我的 代码 优化 | 更新日期: 2023-09-27 18:17:17

为了解决Euler Project n°5问题,我编写了如下程序:

class p5
{
    const int maxNumber = 20;
    static void Main(string[] args)
    {
        Job(); // First warm-up call to avoid Jit latency
        var sw = Stopwatch.StartNew();
        var result = Job();
        sw.Stop();
        Debug.Assert(result == 232792560);
        Console.WriteLine(result);
        Console.WriteLine(sw.Elapsed);
        Console.ReadLine();
    }
    private static int Job()
    {
        var result = Enumerable.Range(1, int.MaxValue - 1)
            .Where(
                n => Enumerable.Range(maxNumber / 2 + 1, maxNumber / 2).All(c => n % c == 0)
            ).First();
        return result;
    }
}

然而,我发现这有点长(17秒,在释放模式下),即使它是工作的。

是否有可能进行优化?

仅供参考,我尝试了AsParallel方法,但正如预期的那样,工作块太小,上下文切换比好处更重(超过1分钟):

    var result = Enumerable.Range(1, int.MaxValue - 1).AsParallel()
        .Where(
            n => Enumerable.Range(maxNumber / 2 + 1, maxNumber / 2).All(c => n % c == 0)
        ).First();
    return result;

[编辑]根据martin的建议,这个版本将花费的时间除以10:

    private static int Job()
    {
        var n =2;
        bool result;
        do
        {
            result = true;
            for (int c = maxNumber / 2; c <= maxNumber; c++)
            {
                if (n % c > 0)
                {
                    result = false;
                    break;
                }
            }
            n ++;//= 2;
        } while (!result);
        return n;
    }

[Edit]总结一下我所有的测试,粗略的执行时间:

  • 我的第一个实现:20秒
  • 删除了内部枚举。范围调用(由一个简单的for循环代替):3秒
  • 删除了外部和内部枚举。呼叫范围:1.5秒
  • 只取偶数(只有循环,没有枚举范围):小于1秒
  • 使用drhirsch建议的Gcd/LCm欧几里德算法:0.004 ms

最新的建议显然是好的答案。我感谢drhirsch提出了另一种方法,而不仅仅是简单的循环优化

可能的优化在我的代码

一个好的优化是使用一个更好的算法。

这是要求数字1的最小公倍数。20,可以通过查找lcm(1,2),然后lcm(lcm(1,2),3)等依次计算,直到20。

求lcm的一个简单算法是用这两个数的乘积除以最大公约数。gcd可以用著名的euklidian算法在很短的时间内找到。
#include <iostream>
long gcd(long a, long b) {
    if (!b) return a;
    return gcd(b, a-b*(a/b));
}
long lcm(long a, long b) {
    return (a*b)/gcd(a, b);
}
int main(int argc, char** argv) {
    long x = 1;
    for (long i=2; i<20; ++i) 
        x = lcm(x, i);
    std::cout << x << std::endl;
}

这个会立刻把溶液喷出来。

嗯,一件事是你只需要测试偶数,所以从0开始,增加2。这是由于一个偶数永远不会被一个奇数整除。你也可以从10的阶乘开始搜索,所以10 * 9 * 8 * 7 . .以此类推,其他单词从10开始!即3 628 800。这可能有助于它运行得更快。而且我用C语言的平均速度是10秒,所以你的代码实际上很好。

使用Enumerable比较慢(参见Enumerable的比较)。重复和for循环初始化数组)。尝试像这样的普通while/for循环:

        int maxNumber = 21;
        int n = 1;
        bool found = false;
        while(!found)
        {
            found = true;
            for(int i = 1; i < maxNumber; i++)
            {
                if(n % i != 0)
                {
                    found = false;
                    break;
                }
            }
            n++;
        }
        return n-1;

在我的计算机调试中运行大约4秒。

编辑

在考虑进一步优化时,最好开始测试较大数字的模,因此当我将for循环更改为:

for (int i = maxNumber; i > 1; i--)

时间下降到2秒以下。

一个数学上的见解是,我们只需要测试非我们已经测试过的数的倍数的数的可整除性。在本例中,我们可以这样写:

    private int[] p = { 19, 17, 16, 13, 11, 9, 7, 5, 4, 3, 2 };
    int Job()
    {
        int n = 1;
        bool found = false;
        while (!found)
        {
            found = true;
            foreach (int i in p)
            {
                if (n % i != 0)
                {
                    found = false;
                    break;
                }
            }
            n++;
        }
        return n - 1;
    }

但是,这实际上更慢,大约2.5秒。