에 에라토스테네스의 체를 최적화 포팅 내가 여기 파이썬에서 (빠른 타오르는) primesieve 사용 전에 어떤 시간 : 지금파이썬에서 C++
def primes2(n):
""" Input n>=6, Returns a list of primes, 2 <= p < n """
n, correction = n-n%6+6, 2-(n%6>1)
sieve = [True] * (n/3)
for i in xrange(1,int(n**0.5)/3+1):
if sieve[i]:
k=3*i+1|1
sieve[ k*k/3 ::2*k] = [False] * ((n/6-k*k/6-1)/k+1)
sieve[k*(k-2*(i&1)+4)/3::2*k] = [False] * ((n/6-k*(k-2*(i&1)+4)/6-1)/k+1)
return [2,3] + [3*i+1|1 for i in xrange(1,n/3-correction) if sieve[i]]
: Fastest way to list all primes below N
가 정확하려면,이 구현을 나는 자동으로 2, 3 등의 배수를 건너 뛰는 최적화에 대한 아이디어를 약간 이해할 수 있지만 C++에이 알고리즘을 이식 할 때는 (나는 Python과 C/C에 대한 합리적인/나쁜 이해를 잘 이해하고있다. ,하지만 락앤롤에 충분히 좋다).
내가 현재 자신을 압연 한 것은이 (isqrt()은 단순한 정수 제곱근 함수)입니다 :
template <class T>
void primesbelow(T N, std::vector<T> &primes) {
T sievemax = (N-3 + (1-(N % 2)))/2;
T i;
T sievemaxroot = isqrt(sievemax) + 1;
boost::dynamic_bitset<> sieve(sievemax);
sieve.set();
primes.push_back(2);
for (i = 0; i <= sievemaxroot; i++) {
if (sieve[i]) {
primes.push_back(2*i+3);
for (T j = 3*i+3; j <= sievemax; j += 2*i+3) sieve[j] = 0; // filter multiples
}
}
for (; i <= sievemax; i++) {
if (sieve[i]) primes.push_back(2*i+3);
}
}
이 구현은 괜찮은 자동으로 2 배수를 건너 뛰고,하지만 난 포트 파이썬 구현을 할 수있는 경우 나는 그것이 훨씬 빠를 수 있다고 생각한다 (50 % -30 % 정도).
우분투 10.10은 1230ms 인 Q6600에N=100000000,
g++ -O3로, 현재 실행 시간을 (이 질문은 성공적으로 응답 될 것입니다 희망에서) 결과를 비교합니다.
위의 파이썬 구현이 무엇인지 이해하거나 나를 위해 이식하는 것이 도움이 될 것입니다.
편집
내가 어려운 무엇을 발견에 대한 몇 가지 추가 정보.
수정 변수와 일반적으로 어떻게 사용되는지 기술에 문제가 있습니다. 서로 다른 Eratosthenes 최적화를 설명하는 사이트에 대한 링크 ("2, 3 및 5의 배수를 건너 뛰고 1000 개의 C 파일로 슬램을 얻는 간단한 사이트는 제외)은 최고 일 것입니다.
나는 100 % 직접 및 글자 그대로의 포트에 문제가 없을 것이라고 생각하지만, 결국 이것은 전혀 쓸모가 없을 것입니다.
편집
원래 NumPy와 버전의 코드보고 후, 실제로 매우 쉽게 구현할 수 및 일부하지 이해하기 너무 열심히 생각으로 있습니다. 이것은 내가 생각해 낸 C++ 버전입니다. 나는 2 백만 라인의 코드가 아닌 매우 효율적인 primesieve를 필요로 할 경우에 대비하여 독자들을 돕기 위해 정식 버전으로 게시하고 있습니다. 이 primesieve는 위와 같은 시스템에서 약 415ms 동안 100000000 미만의 모든 소수를 처리합니다. 3 배의 속도 향상이 예상됩니다.
#include <vector>
#include <boost/dynamic_bitset.hpp>
// http://vault.embedded.com/98/9802fe2.htm - integer square root
unsigned short isqrt(unsigned long a) {
unsigned long rem = 0;
unsigned long root = 0;
for (short i = 0; i < 16; i++) {
root <<= 1;
rem = ((rem << 2) + (a >> 30));
a <<= 2;
root++;
if (root <= rem) {
rem -= root;
root++;
} else root--;
}
return static_cast<unsigned short> (root >> 1);
}
// https://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
// https://stackoverflow.com/questions/5293238/porting-optimized-sieve-of-eratosthenes-from-python-to-c/5293492
template <class T>
void primesbelow(T N, std::vector<T> &primes) {
T i, j, k, l, sievemax, sievemaxroot;
sievemax = N/3;
if ((N % 6) == 2) sievemax++;
sievemaxroot = isqrt(N)/3;
boost::dynamic_bitset<> sieve(sievemax);
sieve.set();
primes.push_back(2);
primes.push_back(3);
for (i = 1; i <= sievemaxroot; i++) {
if (sieve[i]) {
k = (3*i + 1) | 1;
l = (4*k-2*k*(i&1))/3;
for (j = k*k/3; j < sievemax; j += 2*k) {
sieve[j] = 0;
sieve[j+l] = 0;
}
primes.push_back(k);
}
}
for (i = sievemaxroot + 1; i < sievemax; i++) {
if (sieve[i]) primes.push_back((3*i+1)|1);
}
}
파이썬 코드는 단일 요소를 배열로 푸시하지 않습니다. 요소 블록으로 초기화 한 다음 제자리에서 수정합니다. 그것은 C++에서 훨씬 더 빠를 것입니다. 여러분이 가진 것처럼'dynamic_bitset'을 시작하고, 그것을 채우고, 하나의 루프에서 체를 작성하십시오. 아마도 Python 버전의 기술을 복사하지 않고도 훨씬 빠르게 버전을 실행할 수 있습니다. –
파이썬 구현의 어느 부분을 이해하는데 문제가 있습니까? 이 정보를 질문에 추가하십시오. 또한, 사람들은 당신이 말했듯이, 당신의 이해와 많은 도움이되지 않을 것이기 때문에 정말로 당신을위한 항구로 대답해서는 안됩니다. –
@Jeremiah Willcock : 정확하지 않습니다. sieving하는 동안 그것은 내부에서 수정되지만, 결국 배열 (list)'xrange (1, n)의 i에 대해 return [2,3] + [3 * i + 1 | 1]/3-correction)을 사용하면된다. 그리고 그것은 제가하는 일이기도합니다. 첫 번째 루프는 체재 중이며 이미 알고있는 소수를 푸시하고 두 번째 루프는 sievelimit의 루트 이후에 오는 소수를 푸시하는 것입니다. – orlp