왜이 알고리즘이 더 나 빠릅니까? <a href="http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes" rel="nofollow">Wikipedia</a>이에서

Question

은 주어진 알고리즘 중 하나가 소수를 생성하는 것입니다 :

def eratosthenes_sieve(n): 
    # Create a candidate list within which non-primes will be 
    # marked as None; only candidates below sqrt(n) need be checked. 
    candidates = [i for i in range(n + 1)] 
    fin = int(n ** 0.5) 

    # Loop over the candidates, marking out each multiple. 
    for i in range(2, fin + 1): 
     if not candidates[i]: 
      continue 

     candidates[i + i::i] = [None] * (n // i - 1) 

    # Filter out non-primes and return the list. 
    return [i for i in candidates[2:] if i] 

내가 약간 알고리즘을 변경했습니다.

def eratosthenes_sieve(n): 
    # Create a candidate list within which non-primes will be 
    # marked as None; only candidates below sqrt(n) need be checked. 
    candidates = [i for i in range(n + 1)] 
    fin = int(n ** 0.5) 

    # Loop over the candidates, marking out each multiple. 

    candidates[4::2] = [None] * (n // 2 - 1) 

    for i in range(3, fin + 1, 2): 
     if not candidates[i]: 
      continue 

     candidates[i + i::i] = [None] * (n // i - 1) 

    # Filter out non-primes and return the list. 
    return [i for i in candidates[2:] if i] 

나는 처음 2의 모든 배수를 표시하고 나는 단지 홀수 고려했다. 내가 두 알고리즘 (40.000.000 시도)을 타임 아웃했을 때 첫 번째 알고리즘은 항상 더 좋았습니다. 나는 왜 그런지 이해하지 못한다. 누군가 제발 설명해 줄 수 있니?

추신 : 100.000.000을 시도하면 컴퓨터가 정지합니다. 왜 그런가요? 나는 Core Duo E8500, 4GB RAM, Windows 7 Pro 64 Bit를 가지고있다.

업데이트 1 : 이것은 파이썬 3

이다가 업데이트 2 : 이것은 내가 시간이 초과하는 방법입니다

start = time.time() 
a = eratosthenes_sieve(40000000) 
end = time.time() 
print(end - start) 

가 UPDATE

: (특히 nightcracker 윈스턴 Ewert로) 소중한 의견되면 내가가 관리 내가 처음에 의도 코드 :

def eratosthenes_sieve(n): 
    # Create a candidate list within which non-primes will be 
    # marked as None; only c below sqrt(n) need be checked. 
    c = [i for i in range(3, n + 1, 2)] 
    fin = int(n ** 0.5) // 2 

    # Loop over the c, marking out each multiple. 

    for i in range(fin): 
     if not c[i]: 
      continue 

     c[c[i] + i::c[i]] = [None] * ((n // c[i]) - (n // (2 * c[i])) - 1) 

    # Filter out non-primes and return the list. 
    return [2] + [i for i in c if i] 

이 알고리즘에 의해 (맨 위에 언급 한) 원래 알고리즘을 개선 (보통 ly) 50 %. (그래도 나이트 크래커가 언급 한 알고리즘보다 나쁘다.)

파이썬 마스터에게 질문 : 마지막 코드를 좀 더 기능적인 방식으로 표현하는 Python 방식이 있습니까?

업데이트 2 : 나이트 크래커가 언급 한 알고리즘을 디코딩 할 수 없었습니다. 나는 너무 바보 같아.

Answer 1

질문은 왜 더 빠를까요? 두 예제 모두에서 2의 배수로 필터링합니다. candidates[4::2] = [None] * (n // 2 - 1)을 하드 코드했는지 여부 또는 for i in range(2, fin + 1):의 첫 번째 루프에서 실행되는지 여부는 중요하지 않습니다. 당신이 에라 토 스테 네스의 최적화 체에 관심이 있다면

, 여기 당신이 이동 : 여기

def primesbelow(N): 
    # https://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188 
    #""" Input N>=6, Returns a list of primes, 2 <= p < N """ 
    correction = N % 6 > 1 
    N = (N, N-1, N+4, N+3, N+2, N+1)[N%6] 
    sieve = [True] * (N // 3) 
    sieve[0] = False 
    for i in range(int(N ** .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 + 4*k - 2*k*(i%2)) // 3::2*k] = [False] * ((N // 6 - (k*k + 4*k - 2*k*(i%2))//6 - 1) // k + 1) 
    return [2, 3] + [(3 * i + 1) | 1 for i in range(1, N//3 - correction) if sieve[i]] 

설명 : Porting optimized Sieve of Eratosthenes from Python to C++

원래 소스가 here이지만, 아무런 설명이 없었다. 간단히 말해서이 primesieve는 2와 3의 배수를 건너 뛰고 빠른 파이썬 할당을 사용하기 위해 몇 가지 해킹을 사용합니다.

Answer 2

어쨌든 첫 번째 경우에서 수행 한 작업을 수행하기 위해 추가 설정을 수행하기 때문에 속도가 다소 느려질 수 있습니다 (2의 배수로 표시). 그 설정 시간은 당신이 말한 것보다 약간 작을 때 볼 수 있습니다.

Answer 3

여분의 단계는 필요 없으며 실제로 n^1에서 작동하기보다는 'evens' 1/2.

Answer 4

당신은 evens를 피하기 위해 많은 시간을 절약하지 않습니다.알고리즘 내에서 계산 시간의 대부분은이 일을 소요됩니다 :

candidates[i + i::i] = [None] * (n // i - 1) 

그 라인은 컴퓨터의 부품에 대한 행동을 많이 발생합니다. 문제의 숫자가 짝수 일 때마다 if 문에서 루프 베일로 실행되지 않습니다. 따라서 짝수에 대해 루프를 실행하는 데 걸리는 시간은 실제로 매우 작습니다. 이러한 짝수 라운드를 제거해도 루프의 타이밍이 크게 변경되지는 않습니다. 이것이 당신의 방법이 그리 빠르지 않은 이유입니다.

파이썬이 범위에 대해 숫자를 생성 할 때 수식 : start + index * step을 사용합니다. 귀하의 케이스에서와 마찬가지로 두 배를 곱하면 원래 케이스와 같이 약간 더 비쌉니다.

긴 기능을 사용하는 데 약간의 오버 헤드가있을 수 있습니다.

어느 쪽도 속도 문제가 아니지만 버전에 따른 이점은 무시됩니다.