python - sierpinski - reglas de recursividad

Python: se excedió la profundidad máxima de recursión al llamar a un objeto de Python

Question

Construí un rastreador que tenía que ejecutarse en aproximadamente 5 millones de páginas (aumentando el ID de url) y luego analiza las páginas que contienen la información que necesito.

después de usar un algoritmo que se ejecuta en las urls (200K) y guardó los buenos y los malos resultados, encontré que estoy perdiendo mucho tiempo. Pude ver que hay algunos sustitutos recurrentes que puedo usar para verificar la siguiente URL válida.

Puede ver los puntos de interés bastante rápido (un pequeño ejemplo de las primeras "buenas ID") -

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

después de rastrear alrededor de 200K urls que me dieron solo 14K buenos resultados, sabía que estaba perdiendo el tiempo y necesito optimizarlo, así que ejecuto algunas estadísticas y construí una función que verificará las urls al mismo tiempo que aumenta la identificación con 8 / 18 / 17 / 8 (mejores subprendes de retorno), etc. ''.

esta es la funcion

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)

lo que básicamente hace es -checkNextID (ID) es obtener el primer id. Sé que contienen los datos menos 8, por lo que la primera iteración coincidirá con la primera cláusula "if isValid" (isValid (ID + 8) devolverá True).

lastResult es una variable que guarda la última ID de url conocida, por lo que ejecutaremos hasta que numOfRuns sea

isValid () es una función que obtiene un ID + uno de los sustraídos y devuelve True si la url contiene lo que necesito y guarda un objeto de sopa de la url en un varibale global denominado " curRes ", devuelve False si la url no funciona. No contiene los datos que necesito.

parseHTML es una función que obtiene el objeto de sopa (curRes), analiza los datos que necesito y luego guarda los datos en un csv, luego devuelve True.

si isValid () devuelve True, llamaremos a parseHTML () y luego trataremos de verificar el próximo ID + los subtrahends (llamando checkNextID (ID + subtrahends), si ninguno de ellos devolverá lo que estoy buscando, lo haré Auméntelo con 1 y vuelva a verificar hasta que encuentre la siguiente URL válida.

Puedes ver el resto del código here

después de ejecutar el código obtuve unos 950 ~ buenos resultados y, de repente, surgió una excepción:

"algo salió mal: se excedió la profundidad máxima de recursión al llamar a un objeto Python"

Pude ver en WireShark que el fragmento se atascó en la identificación - 510009541 (comencé mi secuencia de comandos con 510000003), la secuencia de comandos intentó obtener la URL con esa ID varias veces antes de que notara el error y la detuviera.

Fue realmente emocionante ver que obtuve los mismos resultados, pero 25x-40x veces más rápido que mi antiguo script, con menos solicitudes HTTP, es muy preciso, solo he perdido 1 resultado por 1000 buenos resultados, que es lo que he encontrado, es imposible de rumiar 5M veces, tuve mi antiguo script ejecutándose durante 30 horas y obtuve 14-15K resultados cuando mi nuevo script me dio 960 ~ resultados en 5-10 minutos.

Leí sobre las limitaciones de la pila, pero debe haber una solución para el algoritmo que estoy tratando de implementar en Python (no puedo volver a mi antiguo "algoritmo" , nunca terminará).

¡Gracias!

Answer 1

En lugar de hacer recursión, las partes del código con checkNextID(ID + 18) y similares podrían reemplazarse con ID+=18 , y luego, si elimina todas las instancias de return 0 , debería hacer lo mismo pero como un simple bucle . Luego, debe colocar un return 0 al final y hacer que sus variables no sean globales.

Answer 2

Puede aumentar la capacidad de la pila de la siguiente manera:

import sys
sys.setrecursionlimit(10000)

Answer 3

Python no tiene un gran soporte para la recursión debido a su falta de TRE ( Eliminación de recursión de cola ).

Esto significa que cada llamada a su función recursiva creará una pila de llamadas de función y porque hay un límite de profundidad de pila (por defecto es 1000) que puede verificar por sys.getrecursionlimit (por supuesto, puede cambiarlo usando sys.setrecursionlimit pero no se recomienda) su programa terminará por fallar cuando llegue a este límite.

Como otra respuesta ya le ha brindado una mejor manera de resolver esto en su caso (que es reemplazar la recursión por un simple bucle), existe otra solución si aún desea usar la recursión, que es usar una de las muchas recetas de Implementando TRE en python como este.

NB: Mi respuesta está destinada a brindarle más información sobre por qué se produce el error, y no le aconsejo que utilice el TRE como ya expliqué, porque en su caso, un bucle será mucho mejor y más fácil de leer.

Answer 4

esto convierte la recursión en un bucle:

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)