Почему мое простое число сито возвращает тот же результат медленнее, чем метод грубой силы для поиска простых чисел в Python 2.7? - PullRequest
Новая
       16

Почему мое простое число сито возвращает тот же результат медленнее, чем метод грубой силы для поиска простых чисел в Python 2.7?

0 голосов
/ 07 декабря 2018

Я довольно новичок в Python, и я пытался найти быстрый способ найти простые числа до заданного числа.

Когда я использую сито Прайма Эратосфена, используя следующий код: 

#Finding primes till 40000.
import time
start = time.time()
def prime_eratosthenes(n):
    list = []
    prime_list = []
    for i in range(2, n+1):
        if i not in list:
            prime_list.append(i)
            for j in range(i*i, n+1, i):
                list.append(j)
    return prime_list

lists = prime_eratosthenes(40000)
print lists
end = time.time()
runtime = end - start
print "runtime =",runtime

Наряду со списком, содержащим простые числа, в качестве вывода я получаю строку, подобную приведенной ниже: 

runtime = 20.4290001392

В зависимости от используемой оперативной памяти и т. Д., Я обычно последовательно получаю значение в диапазоне+ -0,5.

Однако, когда я пытаюсь найти простые числа до 40000, используя метод грубой силы, как в следующем коде: 

import time
start = time.time()
prime_lists = []
for i in range(1,40000+1):
    for j in range(2,i):
        if i%j==0:
            break
    else:
        prime_lists.append(i)
print prime_lists
end = time.time()
runtime = end - start
print "runtime =",runtime

На этот раз вместе со спискомпростые числа, я получаю меньшее значение для времени выполнения: 

runtime = 16.0729999542

Значение изменяется только в диапазоне + -0,5.

Очевидно, что сито медленнее, чем метод грубой силы.

Я также заметил, что разница между временем выполнения в этих двух случаях увеличивается только с увеличением значения 'n', до которого нужно найти простые числа.

Может ли кто-нибудь дать логическое объяснениевыше мпредполагаемое поведение?Я ожидал, что сито будет функционировать более эффективно, чем метод грубой силы, но, похоже, здесь он работает наоборот.

1 Ответ

0 голосов
/ 07 декабря 2018

Хотя добавление к списку не лучший способ реализовать этот алгоритм (оригинальный алгоритм использует массивы фиксированного размера), это амортизированное постоянное время .Я думаю, что большая проблема - if i not in list, что является линейным временем.Лучшее изменение, которое вы можете сделать для больших входов, - это проверить только внешнюю петлю for sqrt(n), что экономит много вычислений.

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

Например: 

def sieve(n):
    nums = [0] * n
    for i in range(2, int(n**0.5)+1):
        if nums[i] == 0:
            for j in range(i*i, n, i):
                nums[j] = 1

    return [i for i in range(2, n) if nums[i] == 0]

Итак, чтобы ответить на ваш вопрос, ваши два цикла for заставляют алгоритм выполнять потенциально O (n^ 2) работа, хотя умный подход к внешнему циклу for заставляет новый алгоритм занимать до O (n sqrt (n)) времени (на практике для n разумного размера время выполнения ближе к O (n))

...