Python: максимальная глубина рекурсии превышена при вызове объекта Python
Я построил сканер, который должен был запускаться на 5M страницах (путем увеличения идентификатора URL), а затем анализирует страницы, содержащие информацию "Мне нужно".
после использования алгоритма, который работает на URL (200K) и сохранил хорошие и плохие результаты, я обнаружил, что я трачу много времени. Я мог видеть, что есть несколько возвращающих вычитаний, которые я могу использовать для проверки следующего действительного URL.
вы можете видеть вычитания довольно быстро (немного ex 'из нескольких первых "хороших идентификаторов" ) -
510000011 # +8
510000029 # +18
510000037 # +8
510000045 # +8
510000052 # +7
510000060 # +8
510000078 # +18
510000086 # +8
510000094 # +8
510000102 # +8
510000110 # etc'
510000128
510000136
510000144
510000151
510000169
510000177
510000185
510000193
510000201
после сканирования около 200 тыс. URL-адресов, которые дали мне только 14 КБ хороших результатов, я знал, что трачу свое время и нуждаюсь в его оптимизации, поэтому я запускаю статистические данные и создаю функцию, которая проверяет URL-адреса, увеличивая идентификатор с помощью 8\18\17\8 (верхние возвращаемые вычеты) и т.д.
это функция -
def checkNextID(ID):
global numOfRuns, curRes, lastResult
while ID < lastResult:
try:
numOfRuns += 1
if numOfRuns % 10 == 0:
time.sleep(3) # sleep every 10 iterations
if isValid(ID + 8):
parseHTML(curRes)
checkNextID(ID + 8)
return 0
if isValid(ID + 18):
parseHTML(curRes)
checkNextID(ID + 18)
return 0
if isValid(ID + 7):
parseHTML(curRes)
checkNextID(ID + 7)
return 0
if isValid(ID + 17):
parseHTML(curRes)
checkNextID(ID + 17)
return 0
if isValid(ID+6):
parseHTML(curRes)
checkNextID(ID + 6)
return 0
if isValid(ID + 16):
parseHTML(curRes)
checkNextID(ID + 16)
return 0
else:
checkNextID(ID + 1)
return 0
except Exception, e:
print "somethin went wrong: " + str(e)
то, что в основном делает, это -checkNextID (ID) получает первый идентификатор, который я знаю, который содержит данные минус 8, поэтому первая итерация будет соответствовать первому "if isValid" (isValid (ID + 8) вернет True).
lastResult - это переменная, которая сохраняет последний известный идентификатор URL-адреса, поэтому мы будем работать до тех пор, пока numOfRuns не будет
isValid() - это функция, которая получает идентификатор + один из вычитаемых значений и возвращает True, если url содержит то, что мне нужно, и сохраняет объект супа url в глобальной varibale с именем - curRes ', он возвращает False, если url не содержит данные, которые мне нужны.
parseHTML - это функция, которая получает объект супа (curRes), анализирует нужные мне данные и затем сохраняет данные в csv, а затем возвращает True.
если isValid() возвращает True, мы будем называть parseHTML(), а затем попытаемся проверить следующий идентификатор + вычитаемые значения (вызывая checkNextID (ID + subtrahends), если ни один из них не вернет то, что я ищу Я увеличу его с помощью 1 и снова проверьте, пока не найду следующий правильный URL.
вы можете увидеть остальную часть кода здесь
после запуска кода я получил около 950 ~ хороших результатов, и внезапно возникло исключение -
"что-то пошло не так: максимальная глубина рекурсии была превышена при вызове Объект Python"
Я мог видеть на WireShark, что scipt застрял на id - 510009541 (я начал свой script с 510000003), script пытался получить URL с этим ID несколько раз, прежде чем я заметил ошибку и остановил ее.
Мне было очень интересно увидеть, что у меня такие же результаты, но в 25 раз-40 раз быстрее, чем у моего старого script, с меньшим количеством HTTP-запросов, это очень точно, я пропустил только 1 результат за 1000 хороших результатов, что найти меня, невозможно рупором 5M раз, у меня был старый script бег на 30 часов и получил 14-15K результатов, когда мой новый script дал мне 960 ~ результат за 5-10 минут.
Я читал о ограничениях стека, но должно быть решение для алгоритма, который я пытаюсь реализовать в Python (я не могу вернуться к моему старому алгоритму, он никогда не закончится).
Спасибо!
Ответы
Ответ 1
это превращает рекурсию в цикл:
def checkNextID(ID):
global numOfRuns, curRes, lastResult
while ID < lastResult:
try:
numOfRuns += 1
if numOfRuns % 10 == 0:
time.sleep(3) # sleep every 10 iterations
if isValid(ID + 8):
parseHTML(curRes)
ID = ID + 8
elif isValid(ID + 18):
parseHTML(curRes)
ID = ID + 18
elif isValid(ID + 7):
parseHTML(curRes)
ID = ID + 7
elif isValid(ID + 17):
parseHTML(curRes)
ID = ID + 17
elif isValid(ID+6):
parseHTML(curRes)
ID = ID + 6
elif isValid(ID + 16):
parseHTML(curRes)
ID = ID + 16
else:
ID = ID + 1
except Exception, e:
print "somethin went wrong: " + str(e)
Ответ 2
Python не имеет большой поддержки для рекурсии из-за отсутствия TRE (Устранение рекурсии хвоста).
Это означает, что каждый вызов вашей рекурсивной функции создает стек вызовов функций и потому, что существует ограничение на глубину стека (по умолчанию - 1000), которую вы можете проверить с помощью sys.getrecursionlimit
(конечно, вы можете изменить его, используя sys.setrecursionlimit, но это не рекомендуется) ваша программа закончится сбой, когда он достигает этого предела.
Поскольку другой ответ уже дает вам гораздо более хороший способ решения этого вопроса в вашем случае (который заключается в замене рекурсии простым циклом), существует еще одно решение, если вы все еще хотите использовать рекурсию, которая должна использовать один из многие рецепты реализации TRE в python, такие как один.
NB: Мой ответ призван дать вам больше информации о том, почему вы получаете сообщение об ошибке, и я не советую вам использовать TRE, как я уже объяснил, потому что в вашем случае цикл будет быть намного лучше и легко читать.
Ответ 3
Вы можете увеличить емкость стека следующим образом:
import sys
sys.setrecursionlimit(10000)
Ответ 4
Вместо выполнения рекурсии части кода с checkNextID(ID + 18)
и аналогичным могут быть заменены на ID+=18
, а затем, если вы удалите все экземпляры return 0
, тогда он должен сделать то же самое, но как простой петля. Затем вы должны положить return 0
в конец и сделать ваши переменные неглобальными.