이 소수 테스트는 어떻게 코드가 5000 배 빨라 졌습니까?

Question

경고 :이 코드는 오일러 프로젝트 Problem 50의 솔루션입니다. 만약 당신이 그것을 버릇 없게 만들고 싶지 않다면 여기를 보지 마십시오.

여기에는 연속 된 소수의 긴 시퀀스를 검색하는 코드가 있습니다.이 코드는 함께 합계가 소수이기도합니다. 한순간에 합계가 소수인지 테스트해야합니다.

나는 computeMaxPrime 함수에서 ifdef가되는 두 개의 테스트를 가지고있다. 첫 번째는 합계를 소수 : : 소수 집합과 비교합니다. 두 번째는 GMP에 의해 구현 된 Miller-Rabin 테스트를 사용합니다. 함수는 6 번만 호출됩니다. 첫 번째 테스트를 사용할 때 computeMaxPrime 함수는 0.12 초 걸립니다. 두 번째 테스트를 사용하면 ~00002 초 밖에 걸리지 않습니다. 누군가 가능한 방법을 설명 할 수 있습니까? 나는 숫자가 집합에 있는지를 확인하기 위해 6 번의 호출이 100ms가 걸릴 것이라고 생각하지 않는다. 나는 또한 unordered_set을 사용하여 시도했고, 같은 것을 수행했다.

어쩌면 타이밍 문제라고 생각했지만 터미널 (OSX)에서 전체 프로그램 실행을 타이밍을 통해 확인했습니다. 나는 또한 내가 Miller-Rabin 테스트를 먼저 사용하도록 테스트를 변경 한 다음 세트를 사용하여 확인하면 세트에 대한 단일 호출을 생성하고 시계가 .02 초를보고 정확히 내가 기대했던 것 (1/6 번째 세트 테스트 만 사용하는 시간).

#include "PrimeGenerator2.h" 
#include <set> 
#include <stdio.h> 
#include <time.h> 
#include <gmp.h> 

typedef std::set<u_int64t>  intSet; 

bool isInIntSet (intSet  set, 
       u_int64t  key) 
{ 
    return (set.count(key) > 0); 
} 

bool isPrime (u_int64t key) 
{ 
    mpz_t  integ; 

    mpz_init (integ); 
    mpz_set_ui (integ, key); 
    return (mpz_probab_prime_p (integ, 25) > 0); 
} 

void computeInitialData (const u_int64t limit, 
         intSet  *primeSet, 
         intList  *sumList, 
         u_int64t *maxCountUpperBound) 
{ 
    PrimeSieve  sieve; 
    u_int64t  cumSum = 0; 
    u_int64t  pastUpperBound = 0; 

    *maxCountUpperBound = 0; 

    for (u_int64t prime = sieve.NextPrime(); prime < limit; prime = sieve.NextPrime()) { 
    primeSet->insert(prime); 

    cumSum += prime; 
    sumList->push_back(cumSum); 
    if (cumSum < limit) 
     (*maxCountUpperBound)++; 
    else 
     pastUpperBound++; 
    } 
} 

u_int64t computeMaxPrime (const u_int64t limit, 
          const intSet &primeSet, 
          const intList &sumList, 
          const u_int64t maxCountUpperBound) 
{ 
    for (int maxCount = maxCountUpperBound; ; maxCount--) { 
    for (int i = 0; i + maxCount < sumList.size(); i++) { 
     u_int64t sum; 

     sum = sumList[maxCount + i] - sumList[i]; 
     if (sum > limit) 
     break; 
#if 0 
     if (isInIntSet (primeSet, sum)) 
     return sum; 
#else 
     if (isPrime (sum)) 
     return sum; 
#endif 
    } 
    } 

    return 0; // This should never happen 
} 

u_int64t findMaxCount (const u_int64t limit) 
{ 
    intSet  primeSet; // Contains the set of all primes < limit 
    intList  sumList; // Array of cumulative sums of primes 

    u_int64t  maxCountUpperBound = 0; // Used an initial guess for the maximum count 
    u_int64t  maxPrime;   // Final return value 

    clock_t  time0, time1, time2; 

    time0  = clock(); 
    computeInitialData (limit, &primeSet, &sumList, &maxCountUpperBound); 
    time1  = clock(); 
    maxPrime = computeMaxPrime (limit, primeSet, sumList, maxCountUpperBound); 
    time2  = clock(); 

    printf ("%f seconds for primes \n" , (double)(time1 - time0)/CLOCKS_PER_SEC); 
    printf ("%f seconds for search \n" , (double)(time2 - time1)/CLOCKS_PER_SEC); 

    return maxPrime; 
} 

int main(void) 
{ 
    printf ("%lld\n", findMaxCount(1000000)); 
} 

편집 : 오 더 이상합니다. STL 세트와 아무 관련이없는 것으로 보입니다. isInIntSet이 호출 된 횟수를 확인하기 위해 해킹을하면 GMP 테스트에 비해 속도가 똑같습니다. 이것은 제가 가능성이 단지 컴파일러의 버그를 통해 실행했다고 생각한다 (EDIT2 : 컴파일러를 비난하지 마십시오!)

bool isInIntSet (intSet set, u_int64t key) 
{ 
    static int counter = 0; 
    counter++; 
    return (counter == 6); 
} 

Answer 1

뜨아합니다. isInIntSet 함수는 intSet를 인수로 직접 취하므로 전체 세트가 복사됩니다. 나는 참조로 전달하려고했다 (intSet & 세트). unordered_set을 사용하면 검색 시간이 .000003 초가됩니다.