Почему мой скрипт прекращает выполнение после 33178210-й итерации?
Я пишу программу на Python, чтобы найти и вернуть список простых чисел-близнецов между двумя числами.
Это мой код:
#prime selector
def is_prime(num):
if num < 2 or num % 2 == 0:
return False
if num == 2:
return True
upr_lmt = int((num ** 0.5) + 1)
for number in range(3, upr_lmt, 2):
if num % number == 0:
return False
return True
def primeLister(end_point, st_point = 2):
primeList = []
for i in range(st_point, end_point + 1):
if is_prime(i):
primeList.append(i)
return primeList
Он сохраняется как prime_selector.py в папке.
Это тестовый пример, который я написал:
# Test case
from prime_selector import primeLister
def log_newline(file_writer):
file_writer.write("\n\n")
def log_testcase(case_num, case_desc, result, file_writer):
file_writer.write(f"================= Test Case {case_num + 1} =================\n")
print((f"================= Test Case {case_num + 1} ================ = "))
file_writer.write(case_desc)
print(case_desc, end = "")
file_writer.write(result)
print(result)
num_list = [99991,999999937]
with open("./primeLister_testcase","w") as file_writer:
for case_num, i in enumerate(num_list):
case_desc = f"Listing all prime numbers till {i}:\n"
result = "".join([f" > {prime}\n" for prime in primeLister(i)])
log_testcase(case_num, case_desc, result, file_writer)
if case_num + 1 != len(num_list):
log_newline(file_writer)
Тестовый пример также сохраняется в той же папке локально.
Программа резко останавливается во время выполнения тестового примера primeLister после записи в файл простых чисел до 99991.
Я предполагаю, что он останавливается в процессе перечисления простых чисел между 99991 и 999999937. Понятия не имею, почему. Мой компьютер оснащен процессором Intel i5-12450H с 16 ГБ оперативной памяти. Если это актуально.
Я уже пробовал реализовать бесконечный цикл, многопоточность, а также использовать обработку исключений. Пока ничего не помогло. Что я делаю неправильно?
Я ожидал, что программа продолжит выполнение, пока не найдет все простые числа в заданном диапазоне.
Пожалуйста, прочитайте минимальный воспроизводимый пример и сосредоточьтесь на слове «Минимальный». Удалив ненужный код, вы можете решить проблему самостоятельно.
Зачем вам цикл while True, чтобы снова повторить все с нуля? Зачем создавать тему? Как это поможет протестировать ваш код? Пожалуйста, удалите все, что не способствует демонстрации проблемы. Запускайте только с одним входом и только один раз и проверяйте только то, что не удалось.
Пожалуйста, укажите «резко останавливается». Есть ли исключение или оно просто в буквальном смысле прекращается?
@SIGHUP это буквально просто останавливается.
@KshitijJha Чтобы быть абсолютно ясным. Перестает ли он выдавать какой-либо результат или процесс завершается? Другими словами, уверены ли вы, что это не происходит в каком-то узком цикле? Какая у вас операционная система?
@SIGHUP Он выдает результат для 99991, начинает обработку вывода для 999999937, держит его около часа, а затем просто останавливается. Никакого дальнейшего вывода, никаких исключений, процесс завершается. Я почти уверен, что процесс запущен для проверки того, является ли число простым, используя is_prime и добавляя его к prime_list. Это считается жесткой петлей? Моя ОС имеет 64-битную архитектуру Win 11.
@trincot Здесь обновлен код, удалены все лишние части. Ошибка все еще проявляется. Я добавил это while True, потому что мне надоело перезапускать весь процесс снова и снова, поэтому он автоматически перезапускается, если останавливается, и я также хотел посмотреть, имеет ли это какое-либо значение. Если бы я хотел внести какие-либо изменения, я всегда мог использовать Ctrl+C для завершения программы.
@nocomment Спасибо, что указали на это. Twin_Primes должен был быть проверен следующим, если тестовый пример для primeLister. Я отредактирую это через мгновение.
Вы говорите о том, что «ошибка все еще возникает»... Вы хотите сказать, что получаете сообщение об ошибке? Или вы говорите, что алгоритм настолько медленный, что не завершается в разумные сроки, и процессу не хватает памяти, или он завершается из-за некоторого ограничения по времени. Если последнее, то запускаете ли вы это на своем локальном движке Python или в какой-то размещенной среде? Вы следили за используемой памятью?
Вы найдете несколько очень интересных функций генерации простых чисел здесь Даже самой эффективной из них (SieveOfAtkin_Arty_Numba) потребуется ~3 минуты (Apple M2) для генерации всех простых чисел до 999999937. Учитывая очевидную неэффективность вашего алгоритма генерации простых чисел , я сильно подозреваю, что ваша программа не остановилась, а просто потребляет огромное количество ресурсов ЦП и/или ОЗУ.
@SIGHUP Просто любопытно: сколько времени у вас занимает этот? На этом сайте это занимает около 41 секунды.
Процесс завершается... с каким статусом завершения или сигналом? Если вам не хватает памяти, вам следует получить SIGKILL, и мы сможем его найти.
Откуда вы знаете, что выполнение прекращается после 33178210-й итерации?
Этот вопрос похож на: Что убило мой процесс и почему?. Если вы считаете, что это другое, отредактируйте вопрос, поясните, чем он отличается и/или как ответы на этот вопрос не помогают решить вашу проблему.
В этом коде все еще есть функции, которые кажутся не связанными с вашей проблемой: случай 99991, по-видимому, работает нормально, поэтому вы можете его пропустить. Нужен только один неудачный случай. Файловый ввод-вывод кажется несвязанным. Можете ли вы подтвердить, возникает ли проблема при удалении всех файловых операций ввода-вывода? Создание одной длинной строки в качестве вывода: связано ли это с вашей проблемой? Возникает ли проблема, когда вы не создаете эту строку? Если нет, пожалуйста, удалите это. Таким образом, продолжайте сокращать код, чтобы получить только минимальный код, который все еще вызывает проблему.
Ответы 2
Если ваша цель — сгенерировать простые числа до определенного числа, использование Sieve или Eratosthenes будет гораздо более эффективным подходом, который также может решить проблему внезапной остановки программы:
def sieve_of_eratosthenes(end_point):
sieve = [True] * (end_point+ 1)
sieve[0] = sieve[1] = False # 0 and 1 are not primes
for start in range(2, int(end_point**0.5) + 1):
if sieve[start]:
for multiple in range(start*start, end_point+ 1, start):
sieve[multiple] = False
return [num for num, is_prime in enumerate(sieve) if is_prime]
Значит, мне следует использовать в своем коде «Решето Эратосфена» вместо primeLister() и is_prime()? Я имею в виду, что понимаю, что это проще и более эффективный способ, чем просто перебирать нечетные числа и исключать их, если они не являются простыми числами. Но я до сих пор не знаю, в чем проблема с моим кодом. И есть вероятность, что я снова столкнусь с этой ошибкой.
Трудно диагностировать проблему с вашим кодом без трассировки стека или минимального воспроизводимого примера, поэтому я предложил возможное исправление, которое значительно ускорит ваш код. Сито заменит праймлистер. Что касается причины, я думаю, что процесс завершается из-за использования слишком большого количества памяти вашего компьютера.
Проблема в том, что ваш процесс стремится создать около 50 миллионов простых чисел для ввода 999999937, накапливая их в списке, и делает это неоптимальным способом, как и для каждого целого числа 𝑘 между 1 и 999999937, которое вы вызываете is_prime, который выполняется √𝑘/2 итерации, когда 𝑘 простое число.
Затем, после долгой работы, вы объединяете эти 50 миллионов чисел с их десятичным представлением в одну длинную строку длиной около 500 миллионов символов. Это половина ГБ, если предположить, что представление символов составляет 1 байт. Возможно, вашей программе не хватает памяти... если она вообще когда-нибудь завершит выдачу простых чисел.
Запустив ваш код с небольшой адаптацией, превратив primeLister в генератор, а затем распечатав простые числа одно за другим (ну, я печатал только одно на 100000, чтобы сэкономить время), я мог следить за прогрессом, я получил, что сгенерировал первый миллион простые числа заняли около 2 минут, а продолжалось это так:
На этом я остановился, но, экстраполируя, прикидываю, что завершение вызова primeLister с вводом 999999937 займет около 22 часов, и только тогда из него будет создана строка размером 0,5 ГБ. Я предполагаю, что ваша система просто убивает процесс из-за нехватки памяти или времени. В моем тесте он не отключился за 15 минут, пока я его ждал. Потом я убил его сам.
Но очевидно, что это непрактично. Вам следует использовать сито.
Но как все это исчерпает их 16 ГБ оперативной памяти?
@nocomment Оценка одного байта на число очень консервативна; Python реально использует гораздо больше байтов на объект.
Конечно, я оцениваю 40 байт на объект int и 72 байта на объект str (включая 8 байт на объект для ссылки в списке). Но 50 миллионов из них плюс большая строка — это всего лишь ~6,3 ГБ. И они сказали, что это прекратилось через час, так что, скорее всего, они еще не дошли до струнной стадии. Возможно, у них было ~10 миллионов целых чисел, и поэтому они использовали только ~0,4 ГБ.
Непонятно, что именно происходит и что в этом удивительного. Вероятно, здесь гораздо больше кода, чем необходимо для воспроизведения проблемы.