Google AdSense (text)

hidden logo stop

Moving

거지 같은 이글루스 광고노출 정책이 싫어서,
새 보금자리(http://blog.leocat.kr/)로 이사감.

[오일러 프로젝트] 1번 문제 Computer & Program

우연히 오일러 프로젝트 1번 문제를 봤는데.. (1부터 1000 미만의 숫자들 중에 3의 배수와 5의 배수의 합을 구하시오)
문득 이런 생각이 떠올랐다. 루프를 돌 때 1, 2, 3, 4, 5, ... 이렇게 1씩 증가하지 말고, 한두개씩 건너 뛰면 어떠까?? 3의 배수는 3, 6, 9, ... 하면 1/3으로 줄어드니까.. 그럼 좀 빨라지나?? 해보자.. 그냥 궁금해졌다.


package test.test;

public class NumberTest
{
    public static void main(String [] args)
    {
        int TIMES = 100;
        int MAX = 1000000000;
        
        
        
        long totalElapsed = 0;
        for(int i=0 ; i<TIMES ; i++)
        {
            totalElapsed += test(MAX);
        }
        
        System.out.println();
        System.out.println(TIMES + " Times");
        System.out.println("Average: " + (totalElapsed / TIMES));
    }
    
    public static long test(int max)
    {
        long sum = 0;
        
        long started = System.currentTimeMillis();
//        sum = method1(max);    // 2500 - 2900ms
//        sum = method2(max);    // 390ms
//        sum = method3(max);    // 570ms
        sum = method4(max);    // 343ms
        long finished = System.currentTimeMillis();
        
        long elapsed = finished - started;
        System.out.println("elapsed: " + elapsed);
        System.out.println("sum: " + sum);
        return elapsed;
    }
    
    public static long method1(int max)
    {
        long sum = 0;
        for(int i=0 ; i<max ; i++)
        {
            if(0 == i % 3 || 0 == i % 5)
                sum += i;
        }
        return sum;
    }
    
    public static long method2(int max)
    {
        long sum = 0;
        int count = 0;
        
        for(int i=0 ; i<max ; i=i+3, count++)
            sum+=i;
        for(int i=0 ; i<max ; i=i+5, count++)
            sum+=i;
        for(int i=0 ; i<max ; i=i+15, count++)
            sum-=i;
        
        System.out.println("count: " + count);
        return sum;
    }
    
    public static long method3(int max)
    {
        long sum = 0;
        for(int i=0 ; i<max ; i=i+3)
            sum+=i;
        for(int i=0 ; i<max ; i=i+5)
            if(0 != i % 3)
                sum+=i;
        return sum;
    }
    
    public static long method4(int max)
    {
        long sum = 0;
        int count = 0;
        
        int times = (int) (max / 3);
        if(0 == max % 3) times--;
        for(int i=1 ; i<=times ; i++, count++)
            sum += (i * 3);
        
        times = (int) (max / 5);
        if(0 == max % 5) times--;
        for(int i=1 ; i<=times ; i++, count++)
            sum += (i * 5);
        
        times = (int) (max / 15);
        if(0 == max % 15) times--;
        for(int i=1 ; i<=times ; i++, count++)
            sum -= (i * 15);
        
        System.out.println("count: " + count);
        return sum;
    }
}


그냥 대충 생각난 방법 4가지인데.. method1은 1부터 끝까지 순차적으로 돌면서 3 또는 5의 배수인지 modulo(%) 연산으로 체크.. 역시 모든 수를 비교해보니 느리다.

그래서 처음 생각난 method2는 루프를 건너뛰면서 무조건 더해봤다. 3과 5의 최소공배수인 15의 배수는 다시 빼주고.. 여기서 처음 시작할 때 가정은 method2는 method1 보다 루프를 도는 횟수가 적다는 것이다. 1 부터 100까지의 값을 구할 때 method1은 100번 돌지만, method2는 3의배수 33번, 5의 배수 20번, 15의 배수 6번으로 모두 합하면 59번 루프를 돈다.

혹시나 15의 배수를 처음부터 안 더해주면 어떨까?? 하는 생각으로 method3을 만들어 봤는데, 성능은 method2 보다 안 좋은 것 같다. modulo 연산도 적게 하려고 5의 배수 루프에 넣었는데.. modulo 연산이 성능이 안 좋은건가.. 조건문이 있어서 그런가.. 신기하다..

그리고 또 갑자기 생각난 method2의 변형이 method4인데.. 루프를 최대값까지 도는게 아니라, 각 배수의 값을 더할 횟수(times라는 지역변수)를 먼저 구하고 그 횟수만큼 루프를 돌려봤다. 그런데 놀랍게도 성능이 더 좋다?? 이거 먼가 이상하다.. 루프를 돌면서 곱하기 연산을 해야 하기 때문에 method2 보다 느릴 것 같았는데..

뭐지?? 아무리 곰곰히 생각해 봐도 모르겠다. 루프를 도는 횟수가 다른지 count를 세봐도 비슷하다. 망할.. 괜한 호기심에 한 번 해봤다가 이거 더 머리가 복잡해졌다. TㅅT


+ 성능 확인은 제 노트북에서 했으니 각자 컴터 마다 다를거에요~ ㅋ

덧글

댓글 입력 영역

Google AdSense (text/image)