Реализация медленного сита Эратосфена. Почему? - PullRequest
Новая
       65

Реализация медленного сита Эратосфена. Почему?

0 голосов
/ 05 февраля 2020

Я хотел реализовать Сито Эратосфена до его базового уровня c без оптимизации при проверке до квадрата root или аналогичного.

Я не понимаю, почему эта реализация такая медленная. .. Требуется около 110 секунд, чтобы запустить сито в течение 10 ^ 5, что значительно медленнее, чем аналогичные реализации.

Может кто-нибудь попытается объяснить, где виновник? 

def sieve(n, out = True):
    start_time = time.time()
    isPrime = [True] * (n-1) # (n-1) since we do not include 0 or 1
    p = 2

    while True:
        multiplier = 2
        multiple = p*multiplier
        # mark all multiples of p as False
        while multiple <= n:
            isPrime[multiple-2] = False # subtract 2 since the list starts at 2. Hence indices and numbers are shifted by 2
            multiplier +=1
            multiple = p*multiplier
        # change p to next prime
        for i, prime in enumerate(isPrime):
            if prime and i+2>p: #remember indices are off by 2 
                p = i+2
                break
        else:
            break
    end_time = time.time()
    if out:
        for i, prime in enumerate(isPrime):
            if prime:
                print(i+2)

    print("Computation took: %0.05f" % (end_time- start_time))

Ответы [ 2 ]

2 голосов
/ 05 февраля 2020

Вы делаете больше работы, чем необходимо. Вы преобразовали сложение в умножение при просеивании, и начальная и конечная точки просеивания больше, чем необходимо. Вот моя реализация, которая исправляет эти проблемы, а также обрабатывает 2 как особый случай: 

def primes(n): # sieve of eratosthenes
    i, p, ps, m = 0, 3, [2], n // 2
    sieve = [True] * m
    while p <= n:
        if sieve[i]:
            ps.append(p)
            for j in range((p*p-3)/2, m, p):
                sieve[j] = False
        i, p = i+1, p+2
    return ps
1 голос
/ 05 февраля 2020

Просто упростите код, и он будет go быстрым: 

from time import time
def sieve(n, out = True):
    start_time = time()
    isPrime = [True] * (n + 1) 

    for p in range(2, n + 1):
        for multiple in range(p * 2, n + 1, p):
            isPrime[multiple] = False

    end_time = time()
    if out:
        for i, prime in enumerate(isPrime):
            if prime and i > 1:
                print(i)

    print("Computation took: %0.05f" % (end_time- start_time))

Вычисление заняло: 0,09900 секунд

...