Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
556 views
in Technique[技术] by (71.8m points)

c# - Possible optimization in my code?

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

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

Is there any possible optimization ?

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;

[Edit] 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;
    }

[Edit] To sum up all my tests, rough execution time :

  • 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

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

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

A good optimization would be using a better algorithm.

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.

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

This spits out the solution instantly.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...