Время выполнения простого алгоритма поиска в Python
Сегодня я столкнулся с этой проблемой, и ни одно из описанных решений не сработало для меня. Итак, вот еще одна возможная причина:
Если у вас есть что-то вроде
AddHandler x-mapp-php6 .php3 .php4 .php .phtml
в файле .htaccess папки вашего веб-содержимого, это может привести к тому, что ваши скрипты PHP перестанут работать , В моем случае сервер не знал тип x-mapp-php6, так как этот файл .htaccess был чем-то импортированным с другого веб-хоста, когда я передал содержимое веб-сайта.
Просто удалив строку AddHandler из файла .htaccess решил это для меня.
1 ответ
Конечно, в интерпретируемом языке, таком как Python, дела идут медленнее - иногда вы можете потерять один или два порядка производительности по сравнению с эквивалентной реализацией языка Си. Однако ваш алгоритм асимптотически намного хуже, чем необходимо. Ваш алгоритм - O(n), но, проверяя делимость только до квадратного корня из n, вы можете достичь O(sqrt(n)) времени. Вы также можете ускорить это за счет некоторых постоянных факторов, применяя факторизацию колес. Колеса {2, 3} и {2, 3, 5} довольно распространены, но вы получаете убывающую отдачу, когда добавляете больше простых чисел к колесу. Для простоты использования колеса {2} мы можем пропустить все четные числа (кроме 2), поскольку ни одно из них не будет простым.
def is_prime(n):
if n < 3:
return n == 2
if not n % 2:
return False
for i in range(3, int(n ** 0.5) + 2, 2):
if not n % i:
return False
return True