Загадки Python - Генерация простых чисел!

Загадки Python - Генерация прайм-чисел!

Обычно существует несколько способов решения задач даже пограничной сложности. Как же определить оптимальное и эффективное решение?

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

ПОСТАНОВКА ЗАДАЧИ

Давайте обратимся к одной из фундаментальных проблем математики: определение и генерация набора простых чисел меньше заданного целого числа. Ваша задача - создать эффективный метод (как алгоритмически, так и программно) для оптимизации вычислительных ресурсов.

Математическое определение:
Простое число определяется как любое положительное целое число больше 1, которое не делится ни на какое целое число, кроме 1 и самого себя.

Входной аргумент:

N = 35 (используется в качестве примера)

Ожидаемый результат:

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]

Ограничения:
Нет. Однако обсудите различные методы оптимизации.

РЕШЕНИЕ

Мы начнем с самого простого подхода и будем совершенствовать его для оптимизации решения алгоритмически и программно.

Простейшее решение
Верные приведенному выше определению, мы начинаем с числа 2 и анализируем каждое целое число до N и смотрим, делится ли оно на любое целое число, кроме 1 и самого себя. Если да, то переходим к следующему целому числу. В противном случае мы собираем его как простое число и переходим к следующему числу.

def get_primes(N):
primes = []
for n in range(2,N):
for d in range(2,n):
if n%d==0:
break
else:
primes.append(n)
return primes 

p = get_primes(35)

Очевидно, что приведенный выше код выдает все простые числа ниже N, однако он является довольно простым, проверяя каждое число, что примерно приводит к вычислительной сложности порядка O(N²), как показано на диаграмме ниже. Если N невелико, алгоритм не занимает много времени, но по мере роста N время вычисления всех простых чисел ниже N растет нелинейно. Поэтому большие значения N будут занимать все больше времени.

Информацию о некоторых подходах к бенчмаркингу Python можно найти в этой статье.

Алгоритмическая оптимизация

Объединив то, что мы знаем о простых числах математически, и то, что Python может делать программно, мы можем добиться некоторого снижения вычислительной сложности. Хотя этот анализ относится к генерации простых чисел, аналогичный процесс может быть использован для оптимизации любой вычислительной реализации.

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

1. Любое четное число больше 2 не может быть простым числом (мы можем объединить этот факт с пропуском счета чисел в Python).
2. При нахождении коэффициентов (делители, дающие 0 в качестве остатка) нам нужно проверять делители только до sqrt(N) из-за симметрии факторизации (можно остановиться внутри цикла, когда мы достигнем sqrt(N)).
3. Наконец, при проверке делимости нам нужно рассматривать простые числа только как факторы. Объединив это с №2, мы должны рассматривать простые числа до sqrt(N) как потенциальные делители для проверки делимости.

Существуют и другие алгоритмические оптимизации для генерации простых чисел, но эта статья больше посвящена изучению реализации Python, чем простым числам.

Реализация

Приведенный ниже код реализует эти алгоритмические оптимизации, причем строки четко обозначают, какая техника оптимизации алгоритма реализуется.

def get_primes_opt(N):
primes = []
for n in range(3,N,2): #optimization-1
is_prime = True
for d in primes: #optimization-3
if d*d > n: #оптимизация-2
break
if n%d==0:
is_prime = False
break
if is_prime:
primes.append(n)
return [2] + primes 

Давайте посмотрим, как это отразится на вычислительных ресурсах. Ниже приведен график, на котором показано время выполнения для различных значений N.

Как вы можете видеть, это занимает значительно меньше времени. Не каждое выполнение точно такое же, некоторые прогоны занимают немного больше времени из-за конкурирующего использования ресурсов. В целом, однако, оптимизированный алгоритм работает намного быстрее, чем первоначальная рудиментарная реализация. Эта оптимизация приводит к вычислительной сложности порядка O(log(N)).

Было бы весьма эффектно увидеть их бок о бок, как показано ниже.

Оказывается, что оптимизированное решение примерно в 100 раз быстрее (для максимального значения N, использованного для тестирования), чем рудиментарное неоптимизированное решение. Это может иметь огромное значение для больших значений N.

Программная оптимизация

Конечно, математика приходит на помощь! Но можем ли мы сделать ее более эффективной, переписав нашу функцию по-другому? Да, если ваша задача заключается в многократном вычислении простых чисел при заданном N для многих различных значений N.

Скажем, раньше мы использовали 1000 для N, а теперь нам нужны простые числа до 1200, действительно ли нам нужно снова генерировать все простые числа до 1000? Нет, если вы их где-то храните.

Реализация

Мы можем переписать нашу реализацию как класс, и хранить уже вычисленные простые числа как переменную класса, а повторно генерировать только при необходимости. Реализация для этого показана ниже.

class PrimeNumbers:
def __init__(self):
self.__last_processed_N = 2
self.__next_start = 3
self.__primes = [2]

def __generate_primes__(self, N):
if N <= self.__last_processed_N:
return #нет необходимости генерировать снова для меньших Ns
for n in range(self.__next_start,N,2):
is_prime = True
for d in self.__primes:
if d*d > n:
break
if n%d==0:
is_prime = False
break
if is_prime:
self.__primes.append(n)
self.__last_processed_N = N
self.__next_start = N if N%2 else N+1 

def get_primes(self, N):
self.__generate_primes__(N)
retval = []
for x in self.__primes:
if x >= N:
break
retval.append(x)
return retval 

p = PrimeNumbers(
)p1000 = p.get_primes(1000)
p1200 = p.get_primes(1200)

# последняя строка запускает генерацию простых чисел только для чисел между #1000
и 1200, повторно используя ранее вычисленные простые числа.

В качестве примера для измерения производительности давайте вычислим простые числа для значений N от 100 до 500000 с шагом 1000.

Как вы можете видеть, время значительно сократилось. Давайте посмотрим, как это сопоставимо с оптимизацией только алгоритма (который заново генерирует простые числа каждый раз, когда мы вызываем функцию). Ниже показано боковое сравнение алгоритмической оптимизации и решения Class для инкрементного вычисления в партиях по 1000 чисел.

Как видно из графика, инкрементное вычисление может быть довольно эффективным в определенных сценариях. Например, когда N равно 500000 (последний цикл), оптимизированный алгоритм занял 400 мс, в то время как реализация Incremental Class заняла менее 10 мс (так как рассматривала только последние 1000 чисел в качестве кандидатов) и искала все простые числа ниже 499000 из памяти.

ЗАКЛЮЧЕНИЕ

При внедрении и разработке программ всегда (ВСЕГДА) помните об эффективности. Не нужно тратить лишние вычислительные ресурсы даже для простых реализаций.

Следите за новыми головоломками Python и не забудьте оставить мне сообщение!