Как вы предсказываете время выполнения нелинейного сценария?

Question

Я написал этот простой код на python для вычисления заданного числа простых чисел.

Вопрос, который я хочу задать, состоит в том, могу ли я написать скрипт, который вычисляет как долго потребуется, с точки зрения процессорных циклов, чтобы выполнить это?Если да, то как?

primes = [2]
pstep = 3
count = 1

def ifprime (a):

""" Checking if the passed number is prime or not"""
global primes

for check in primes:
    if (a%check) == 0:
            return False
return True

while 1000000000>= count:

if ifprime(pstep):
    primes.append (pstep)
    print pstep
    count += 1
pstep += 1

Интересной особенностью этой проблемы является то, что найти ли простые числа после x циклов приращения - это почти невозможно предсказать.Более того, в этом сценарии происходит рекурсия, поскольку чем больше «простой» список, тем больше времени потребуется для выполнения этой функции.

Какие-либо советы?

Answer 1

Я думаю, что вам нужно будет использовать приближение распределения простых чисел, например, PNT , которое (я думаю) утверждает, что между 1 и x у вас будет приблизительно x/ln(x) простых чисел (еслинатуральное бревно).Поэтому, учитывая приблизительные оценки времени, затраченного на одну итерацию, вы сможете создать оценку.

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

t (x) ~ x / ln (x) * a + b + t (x-1)

, где t(x) - время, необходимое до и включающей итерации x, a - время, необходимое для проверки каждого простого числа в списке (модульная операция), а b - «постоянное» времяосновной цикл.Я слабо помню, что есть способ преобразовать такие рекурсивные функции в линейные;)

Answer 2

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

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

Answer 3

Когда вы вызываете isprime (pstep), вы выполняете цикл pstep * ln (pstep), если у вас есть простое число, вероятность которого равна 1 / ln (pstep). Таким образом, стоимость тестирования простых чисел пропорциональна шагу. Неизвестна стоимость тестирования композитов, потому что мы не знаем среднего наименьшего коэффициента композитов между 2 и N. Если мы проигнорируем его, предполагая, что в нем преобладают затраты на простые числа, мы получаем общую стоимость SUM (pstep) для pstep = 3 до N + 3, что примерно пропорционально N ** 2.

Вы можете уменьшить это значение до N ** 1,5, обрезав цикл в isprime (), если отмечено> sqrt (a).

Answer 4

Ну, есть большая ветвь теоретической информатики - теория сложности - посвященная именно такой проблеме. Общая проблема (принятия решения о том, завершится ли код для произвольного ввода), у вас здесь состоит в том, что называется «NP-полная» и поэтому очень трудна.

Но в этом случае у вас, вероятно, есть два варианта.

Первое - использовать грубую силу. Запустите timeit для isprime (a) для a=1, 2, 3, 4, ..., постройте график времени и попытайтесь выяснить, не выглядит ли это как-то очевидным: a^2, a log a, что угодно.

Правильный, но более сложный ответ - проанализировать свой алгоритм и посмотреть, сможете ли вы определить, сколько операций требуется для «типичного случая».

Answer 5

Что ж, если вы работаете в Linux, вы можете использовать команду 'time', а затем проанализировать ее результат.

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