construyendo una araña web en profundidad, lo que significa que visitará todos los enlaces en la primera página, vaya a cada enlace y visite los enlaces en la segunda página ...al construir una araña web, ¿deberías usar recursión?
¿Debe usar recursion? Encuentro que es una CPU intensiva.
def recursion()
linkz_on_first_page.each do |link|
recursion(link)
end
end
recursion(firstpage)
No es tanto que la recurrencia sea intensiva en la CPU (en realidad no lo es), sino que hará estallar su pila de llamadas después de unas miles de llamadas recursivas, que fácilmente podría escribir escribiendo una araña web ejecutándose abiertamente Internet.
Ejemplo:
def blow_stack(level=0)
puts "at level #{level}"
blow_stack(level+1)
end
salida de esto en mi MacBook Pro:
irb(main):009:0> blow_stack
at level 0
at level 1
... (skip a bunch of output)
at level 6295
at level 6296
SystemStackError: stack level too deep
from (irb):7:in `blow_stack'
from (irb):7:in `blow_stack'
from (irb):9
from :0
Definitivamente no, vas a tener problemas muy rápidamente debido a la naturaleza real de la red mundial. En el momento en que accedes a un sitio con una sección principal de navegación, donde cada página se vincula a cada página, ingresas un ciclo infinito.
Puede hacer un seguimiento de los enlaces que ha manejado, pero aun así, un bucle recursivo no se ajusta realmente a la naturaleza de la world wide web (aunque a primera vista parece, la web es más una realidad "web" que un árbol). Es mejor que encuentre todos los enlaces en la página actual y agregue esos enlaces (si es que aún no existen) a una cola central, y proceda de forma iterativa a través de la cola procesando cada enlace a medida que llega (recuerde hacer un seguimiento de enlaces que haya terminado de procesar, o los agregará al final de la cola nuevamente)
Mi pensamiento inmediato fue también "cola". Con la posible adición de un poco de inteligencia de deduplicación, espero que también proporcione la base para una capacidad de escalado muy robusta. –
¿cómo creo la cola? ¿Quiere decir crear una gran matriz que contenga todos los enlaces, y antes de navegar a cada enlace, verifique que no se haya visitado antes? – pgh
En teoría, una matriz sería suficiente; en la práctica, tendrá problemas de rendimiento/escalabilidad ya que su cola central será el cuello de botella. Es posible que tenga hash o algo para reducir el tiempo de búsqueda. – sebastiangeiger
La recursión parece ser apropiada, hasta que piense un poco más al respecto. En caso de que tenga una página A que contenga un enlace a la página B y una página B que contenga un enlace a la página A, se encontrará atrapado en un ciclo interminable.
La recursividad ya no requiere más CPU que hacerlo de forma "normal". Tienes que preguntarte si necesitas todos los enlaces o si es suficiente solo para obtener enlaces hasta cierto nivel. En el último caso, esto también resuelve su problema de ciclo sin fin.
Si necesita todos los enlaces, prefiero usar una lista de enlaces en la que cada enlace es único. Su programa toma un enlace de la lista y arañas este enlace. Una vez que se descubre un nuevo enlace, intente insertarlo en esta lista y así sucesivamente.
maldita sea ... demasiado lento. – sebastiangeiger
¿qué pasa si llamo a las pilas y están cerradas adecuadamente? – pgh
No estoy seguro si sigo esa pregunta pgh. Cuando digo "call stack" me refiero a la pila de llamadas a función que la mayoría de los lenguajes (incluido Ruby) usan para rastrear a qué funciones se ha llamado y a dónde volver. Esta pila tiene un tamaño finito (normalmente espacio para unos pocos miles de capas de llamada de método), por lo que si estás realizando recursiones profundas, te quedarás sin espacio en la pila. Esto es diferente a una "pila" regular a la que se accede mediante una función regular no recursiva. Eso funcionaría bien. – madlep