Project Euler 10 - 첫 번째 파이썬 코드가 두 번째 코드보다 훨씬 빠르게 실행되는 이유는 무엇입니까?

Question

오일러 프로젝트 10 번째 문제점 :

10 다음 소수의 합은 2 + 3 + 5 + 7 = 17

은 이백 만 아래의 모든 소수의 합을 찾는다.

sieve = [True] * 2000000 # Sieve is faster for 2M primes 
def mark(sieve, x): 
    for i in xrange(x+x, len(sieve), x): 
     sieve[i] = False 

for x in xrange(2, int(len(sieve) ** 0.5) + 1): 
    if sieve[x]: mark(sieve, x) 

print sum(i for i in xrange(2, len(sieve)) if sieve[i]) 

3 초 동안 실행 here 출판 :

나는이 조각을 발견했다.

def isprime(n): 
    for x in xrange(3, int(n**0.5)+1): 
     if n % x == 0: 
      return False 
    return True 

sum=0; 
for i in xrange(1,int(2e6),2): 
    if isprime(i): 
     sum += i 

내 코드 (두 번째)이 훨씬 느립니다 왜 이해가 안 :

는이 코드를 썼다?

Answer 1

귀하의 알고리즘은 소수로 2에서 N (N = 2000000)의 모든 숫자를 개별적으로 검사합니다.

스 니펫 -1은 약 2200 년 전에 발견 된 sieve of Eratosthenes 알고리즘을 사용합니다. 그것은 모든 번호를 확인하지만,하지 않습니다

• 는
• 가 프라임으로 표시 (2) 첫 번째 숫자를 찾습니다 2000000 2까지의 모든 수의 "체"를 만들고, 그때부터 모든 배수를 삭제 그 체.
• 그런 다음 삭제되지 않은 다음 번호 (3)를 찾아서 프라임으로 표시하고 모든 배수를 체에서 삭제합니다.
• 그런 다음 삭제되지 않은 다음 번호 (5)를 찾아서 프라임으로 표시하고 모든 배수를 체에서 삭제합니다.
• ...
• 프라임 1409가 발견 될 때까지 체에서 모든 배수를 삭제합니다.
• 그러면 1414 ~ = sqrt (2000000)까지의 모든 소수가 발견되어 중지됩니다.
• 1415에서 2000000까지의 숫자는 검사 할 필요가 없습니다. 삭제되지 않은 모든 사람들도 소수입니다.

그래서 알고리즘은 N.까지의 모든 소수를 생성

주의 사항은 어떤 부문 만 추가 (심지어 곱셈, 그리고 너무 작은 숫자 중요하지만 더 큰 때와 수도를하지 않습니다 1). 시간 복잡도는 O(n loglogn)이고 알고리듬은 O(n^(3/2)) (또는 @Daniel Fischer가 언급 한대로 O(n^(3/2)/logn))에 가까운 값을 가지고 있습니다. 단점은 곱셈과 동일하다고 가정합니다. 위키 백과 (위 링크) 기사에서

: 랜덤 액세스 기계 모델

시간 복잡도는 O 작업 (N N 로그 기록), 사실의 직접적인 결과는 prime harmonic series는 점근 적 log log n 접근 것이다.

감사를 @machineyearning

Answer 2

첫 번째 버전은 범위의 모든 소수를 사전 계산하고이를 sieve 배열에 저장합니다. 그런 다음 솔루션에서 소수를 추가하는 간단한 문제입니다. 그것은 memoization의 형태로 볼 수 있습니다.

두 번째 버전은 범위 내의 각 숫자를 테스트하여 소수인지 여부를 확인하고 이전 계산으로 이미 많은 작업을 반복합니다.

결론적으로 첫 번째 버전은 값을 다시 계산하지 않지만 두 번째 버전은 동일한 작업을 반복 수행합니다. 그 숫자는 것에 대해 테스트 할 때 솔루션에서

, 숫자 2는 각 번호에 대해 테스트됩니다

Answer 3

쉽게 차이를 이해하기 위해, 각 번호는 잠재적 인 분할로 사용됩니다 얼마나 많은 시간을 생각하십시오 총리. 길을 따라 지나가는 모든 숫자는 다음 숫자마다 잠재적 인 구분 기호로 사용됩니다.

첫 번째 해결 방법은 한 번 돌이켜 보지 않은 번호를 밟은 후에는 도달 한 곳에서 항상 앞으로 나아갑니다.

mark(sieve, 2) 
for x in xrange(3, int(len(sieve) ** 0.5) + 1, 2): 
    if sieve[x]: mark(sieve, x) 

만 각 번호에 한 번보고 오히려 통해가는 것보다, 앞으로의 곱셈을 모두 지우이 방법 : 그건 그렇고, 가능한 일반적인 최적화는 당신이 표시된 후에 만 ​​홀수 번호를 이동하는 것입니다 모든 가능한 구분선은 이전의 모든 번호와 각 번호를 반복해서 확인하며, if 문은 이전에 발생한 번호에 대해 반복적으로 작업하지 못하도록합니다.

Answer 4

오스카 (Obscar)의 답변에 따르면 알고리즘은 많은 작업을 반복합니다.

calls, count = 0, 0 
def mark(sieve, x): 
    global calls, count 
    calls += 1 
    for i in xrange(x+x, len(sieve), x): 
     count += 1 
     sieve[i] = False 

: 함수가 호출 된 횟수를 추적 mark() 및 isprime() 기능, 다음과 같은 수정 된 버전과 루프 반복을위한의 총 수를 고려 얼마나 다른 알고리즘이 저장 처리를 많이 참조하십시오

이 새로운 함수로 첫 번째 코드를 실행 한 후 mark()이 223 회 호출되고 for 루프에서 총 4,489,006 회 (~ 450 만 회) 반복이 수행됨을 알 수 있습니다.우리는 당신의 코드와 유사한 변경하면

calls, count = 0 
def isprime(n): 
    global calls, count 
    calls += 1 
    for x in xrange(3, int(n**0.5)+1): 
     count += 1 
     if n % x == 0: 
      return False 
    return True 

, 우리는 isprime()가 for 루프의 177,492,735 (~ 177,500,000) 반복과 1,000,000 (100 만) 번 호출되는 것을 볼 수 있습니다.

함수 호출 및 루프 반복 계산은 알고리즘이 더 빠르지 만 일반적으로 적은 단계 == 적은 시간을 결정하는 데 항상 결정적인 방법은 아니며 코드에서 단계 최적화에 몇 가지 최적화 단계를 사용할 수 있습니다.