Улучшение моей реализации сито Eratosthenes - PullRequest
Новая
       8

Улучшение моей реализации сито Eratosthenes

1 голос
/ 15 апреля 2020

Я создаю сито Эратосфена, чтобы более эффективно суммировать простые числа от 1 до большого числа n. Что я хочу сделать, это создать список от 2 до n, а затем удалить кратные 2, затем кратные 3, затем кратные следующего числа в списке, и так далее. Код, который я создал, я думаю, что он очень медленный во времени, это почти как создание списка путем проверки, является ли каждая запись простым числом. Я предполагаю, что количество операций, которые у меня есть, имеет порядок: квадрат root из n (первый, пока l oop) раз (немного меньше) квадрат root из n (для второй, пока l oop ). Поэтому я не уверен, замедляет ли это метод удаления или, возможно, другие вещи.

Мой код такой: 

def sieve_of_Eratosthenes(n):
L= list(range(2,n+1))
# creates a list from 2 to n

i=2
while i*i <=n: # going to remove multiples of i, starting at i^2
    k=i        # if j <i then ij already checked
    while i*k <= max(L):
        try:
            L.remove(i*k)   # there is an error if the element is not in 
                            # the list so need to add these two lines
        except ValueError:  
            pass     # do nothing!
        k=k+1
    i=L[i-1]      # list index starts at 0, want i to be next element in the list
# print(L)
return L

1 Ответ

3 голосов
/ 15 апреля 2020

Предположение

Вопрос в том, как улучшить время работы вашего программного обеспечения, поскольку оно очень медленное.

Выполняется после двух изменения кода ускоряют ваш код

  1. Вместо того, чтобы хранить список простых чисел, проверяйте числа как простые (истинные) или не простые (ложные)
  2. проверяйте только нечетные числа> 2 для простого

Код 

def sieve_of_Eratosthenes2(n):
    if n < 2:
        return []
    if n < 3:
        return [2]

    L = [True] * (n+1)    # all numbers set as primes initially

    # modifies prime flag in list for odd numbers
    for i in range(3, n, 2): # Check odd numbers for prime (no need to check even numbers)
        if L[i]: # A prime
            L[i*i::i] = [False]*len(L[i*i::i]) # from i^2 in increments of i

    # Report prime 2 + odd primes
    return [2] + [i for i in range(3, n, 2) if L[i]]  # Get odd numbers whose flag is 
                                                      # still True

Новый код 

%timeit sieve_of_Eratosthenes2(1000)
188 µs ± 16.6 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
%timeit sieve_of_Eratosthenes2(100000)
16 ms ± 1.58 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

In going from 1, 000 to 100, 000 time 
(i.e. 100X), time increased by ~85, 
so almost linear

Старый код 

 %timeit sieve_of_Eratosthenes(1000)
 25.2 ms ± 1.59 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
 sieve_of_Eratosthenes2(100000)
 261.45 seconds  (using time module)

In going from 1, 000 to 100, 000 (100X)
time increased by factor of ~10, 000
So quadratic increase in time (i.e. 100^2).

Пояснение

Сложность Сито Эратосфена составляет 

O(N log (log N))

Что почти линейно , поскольку операции обычно O (1), чтобы пометить числа в массиве как True (простое число) и False (не простое число).

В исходном алгоритме числа не простые числа были удалены, а не помечены, что занимает : 

O(N) per removal.

Это добавляет дополнительный коэффициент N к сложности Сита Эратосфена, в результате чего оригинальная сложность алгоритма составляет: * 1 046 * 

O(N*N*log (log N))

Таким образом, почти квадратично c, что подтверждается временем выполнения.

...