在我的代码可能的优化？ [英] Possible optimization in my code?

问题描述

为了解决欧拉项目问题N°5 ，我写了下面的程序：

In order to solve the Euler Project problem n°5, I wrote the following program:

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秒，在发布模式），即使它的工作。

However, I found this is a bit long (17 seconds, in release mode), even if it's working.

是否有任何可能的优化？

Is there any possible optimization ?

仅供参考，我试着用进行AsParallel 方法，但如预期，作品块太小和上下文切换比利益更重（多于1分钟）：

FYI, I tried with AsParallel method, but as expected, the chunk of works are too small and the context switch was heavier than the benefits (more that 1 minute) :

    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;

根据马丁的建议，这个版本除以10所花费的时间：

According martin's suggestion, this version divided by 10 the time taken :

    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;
    }

：要总结我所有的测试粗糙的执行时间：

To sum up all my tests, rough execution time :

• 我的第一次执行：20秒


• 删除内enumerable.Range呼叫（通过一个简单的取代了循环）：3秒


• 删除了外部和内部enumerable.Range通话1.5第二个


• 只有走偶数（与循环而已，没有enumerable.range）：小于1秒


• 使用GCD / LCM欧几里德算法，建议的drhirsch：0.004毫秒

• My first implementation : 20 secs
• Removed the inner enumerable.Range call (replaced by a simple for loop): 3 seconds
• Removed the outer and inner enumerable.Range call: 1.5 second
• Only taking even numbers : (with loops only, no enumerable.range) : less than 1 second
• Using Gcd/LCm euclidean algorithms as suggested by drhirsch : 0.004 ms

最新的建议显然是很好的答案。我感谢drhirsch的暗示另一种方法，而不是只有简单​​的循环优化

The latest suggestion is clearly the good answer. I thank drhirsch for suggesting another approach instead of only simple loop optimization

推荐答案

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

A good optimization would be using a better algorithm.

这是要求输入的数字1..20，它可以通过找到的 LCM 的>（1,2），然后LCM（液晶显示模块（1,2），3）等，直到20。

This is asking for the least common multiple of the numbers 1..20, which can be calculated successive by finding lcm(1,2), then lcm(lcm(1,2),3) etc until 20.

一个简单的算法寻找LCM被划分的产品这两个数字的的最大公约数的。在最大公约数的可通过公知的 euklidian算法的在一个非常发现。很短的时间

A simple algorithm for finding the lcm is dividing the product of the two numbers by the greatest common divisor. The gcd can be found by the well known euklidian algorithm in a very short time.

#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;
}

这吐出液瞬间。

这篇关于在我的代码可能的优化？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！