Haciendo scraping en paralelo

Todo el que haya hecho un poco de Web scraping en algunos lenguajes como Python, se habrá topado con un problema muy habitual: las peticiones de red bloqueantes.

Aunque el scraper tarde unos pocos milisegundos en procesar el HTML, tener que descargarse 10 páginas de forma secuencial hace que el tiempo de ejecución crezca considerablemente. Para sortear este problema, hay muchas alternativas. Veamos algunas de ellas con un ejemplo.

Supongamos que queremos descargarnos los primeros 1000 cómics de XKCD. Un script sencillo sería el siguiente:

1 from requests import get
2 
3 URL = "https://xkcd.com/%s/"
4 
5 pages = []
6 for n in range(1, 1001):
7 	print("Downloading page %s" % n)
8 	pages.append(get(URL % n))

El módulo threading

Con este módulo podemos crear varias threads, y hacer muchas peticiones de forma simultánea:

1 from requests import get
2 from threading import Thread
3 
4 URL = "https://xkcd.com/%s/"
5 pages = []
6 
7 def down(n):
8 	print("Downloading page %s" % n)
9 	pages.append(get(URL % n))
10 
11 threads = [Thread(target = down, args = (n,)) for n in range(1, 1001)]
12 [t.start() for t in threads] # start all threads
13 [t.join() for t in threads] # block until all threads finish

Esto acelera considerablemente el programa, que pasa de tardar unos 17 minutos en mi ordenador, a unos aceptables 17 segundos. Pero el problema sigue ahí: si en lugar de 1000 páginas fueran 10000, ¿sería el procesador capaz de manejar tantísimos hilos de forma óptima? ¿daría con un número máximo de threads?.

El módulo threading con workers

Una alternativa es la creación de workers: un número limitado de threads que no descargan una única página, sino que van descargando páginas hasta obtenerlas todas.

1 from requests import get
2 from threading import Thread
3 
4 URL = "https://xkcd.com/%s/"
5 WORKERS = 20
6 pages = []
7 
8 to_download = [URL % n for n in range(1, 1001)]
9 
10 def worker():
11 	while len(to_download):
12 		url = to_download.pop()
13 		print("Downloading page %s" % url)
14 		pages.append(get(url))
15 
16 workers = [Thread(target = worker) for _ in range(WORKERS)]
17 [w.start() for w in workers] # start all workers
18 [w.join() for w in workers] # block until all workers finish

En mi ordenador, tarda unos 21 segundos en hacer la descarga completa, pero la carga del procesador es mucho menor en este caso. Volvemos a la limitación anterior, ante un gran número de páginas a descargar, se vuelve bastante lento. Pero aun nos queda una opción.

El módulo grequests

Este módulo tiene la misma interfaz que requests, con la diferencia de que al importarlo hay que poner una G por delante. Su instalación desde pip es muy sencilla, y permite hacer las peticiones de forma asíncrona mediante la librería Gevent. Al hacer una petición de varias páginas, grequests crea y gestiona las corrutinas para descargarlas.

1 from grequests import get, map
2 
3 URL = "https://xkcd.com/%s/"
4 
5 reqs = [get(URL % n) for n in range(1, 1001)]
6 print("Downloading all pages")
7 print(map(reqs))

Este código es mucho más sencillo e intuitivo que los anteriores. Además, descarga las 1000 páginas en apenas 15 segundos sin sobrecargar el procesador en absoluto.

Cómic de XKCD

Existen otras alternativas que aun no he explorado, como requests-threads y requests-futures. Si conoces más sobre este tema, no dudes en dejar un comentario!

No hay comentarios

Diffchecker: comparando secuencias

Seguramente, si has programado alguna vez usando un repositorio, hayas visto cómo al subir código, existe una herramienta llamada diff, capaz de comparar el código antiguo y el nuevo, y detectar los fragmentos que han cambiado, y aquellos que ambos tienen en común.

Ejemplo de diff checking

Este algoritmo parece sencillo hasta que nos paramos a pensar en su funcionamiento un rato. Por ejemplo, si queremos comparar las palabras schwarzenegger y chuarcheneger, obtenemos el siguiente resultado:

1   ANTES:  s c h w a r z . e n e g g e r
2 DESPUES:  . c h u a r c h e n e g . e r
3 CAMBIOS:  - = = / = = / + = = = = - = =

En el cambio hemos eliminado 2 letras, modificado 2 letras y añadido una letra. Este análisis, que no es tan simple de realizar con nuestra inteligencia natural, tampoco tiene una solución algorítmica trivial.

Subsecuencia común más larga (LCS)

Este es el nombre de este problema en algoritmia, donde se formula como: dadas dos secuencias, encontrar la secuencia más larga que ambas tienen en común.

Como las herramientas de diff sólo comparan entre sí dos cadenas, existe una solución mediante un algoritmo divide y vencerás, que va reduciendo el problema a otros problemas más pequeños. Así, se puede definir el problema de la siguiente forma:

1 def LCS(X, Y):
2     if len(X) == 0 or len(Y) == 0:
3         return []
4     if X[-1] == Y[-1]:
5         return LCS(X[:-1], Y[:-1]) + [X[-1]]
6     else:
7         return longest(LCS(X, Y[:-1]), LCS(X[:-1], Y))

Donde longest es una función que sencillamente devuelve la cadena más larga:

1 def longest(X, Y):
2 	return X if len(X) > len(Y) else Y

Teniendo el algoritmo LCS (que podéis probar en Python), es fácil averiguar qué se ha añadido, eliminado, o modificado al comparar dos cadenas. Sin embargo, es un algoritmo muy lento. Basta con que pongamos dos cadenas algo más largas (como arn. schwarzenegger y ar. chuarcheneger) para que el tiempo de ejecución se dispare.

Por eso es necesario el uso de una memoria que almacene los resultados, a fin de no tener que computarlos más de una vez. Haz la prueba:

Esta es la base de este algoritmo, aunque hay que detallar ciertos matices para que funcione correctamente; convertir el algoritmo recursivo en uno iterativo para evitar exceder el límite de recursión, utilizar estructuras de datos que permitan un cálculo más eficiente, o tokenizar las secuencias para considerar que cada elemento puede ser una fila de código o una palabra en lugar de un caracter.

Y para rizar el rizo, aquí tenéis el resultado de una herramienta de diffcheck, comparando nuestro algoritmo antes y después de usar memoria.

No hay comentarios

Python Challenge: Niveles 15-17

Python Challenge es una página con retos a resolver utilizando Python. Esta es la continuación del post con las soluciones de los niveles 7-14 de este challenge. Puedes encontrar el código de las soluciones en Github.

Nivel 15: Whom?

Encontramos una imagen peculiar, de un calendario del año 1XX6, en el que febrero tuvo 29 días, y el lunes fué día 26. La pista en este caso está en el código fuente, y es "buy flowers for tomorrow ". Ya que la pregunta es whom?, una simple búsqueda en Wikipedia del día 27 de enero nos da una gran lista de personas que nacieron ese día. Si limitamos la búsqueda a años que sigan el patrón 1XX6, y que cayera en lunes, obtenemos un único resultado: el nacimiento de Wolfgang Amadeus Mozart.

Nivel 16: Let me get this straight

Tras varios niveles de este estilo, es bastante intuitivo de resolver. Si unimos toda la imagen en una única cadena de 1px de altura, y vamos introduciendo un salto por cada secuencia repetitiva de píxeles blancos y rosas que encontremos, obtenemos la clave del nivel:

Solución al nivel 16 del Python Challenge

Nivel 17: Eat?

Nos encontramos con una imagen de galletas (pista por excelencia sobre cookies) con una pequeña imagen que hace referencia al nivel 4.

Volviendo a este nivel observamos que una cookie nos dice "you should have followed busynothing". Ya que las urls de este nivel eran del tipo ?nothing=..., cambiamos la primera de ellas por ?busynothing=... y empezamos a seguir la cadena, mientras guardamos la información que nos va dando la cookie info. Obtenemos la siguiente frase:

is it the 26th already? call his father and inform him that "the flowers are on their way". he'll understand.

Una rápida búsqueda y descubrimos que su padre era Leopold Mozart. Ya que nos dice que le llamemos, usamos el teléfono del nivel 13 para llamar a Leopold, que nos dice 555-VIOLIN. Reemplazamos la URL por VIOLIN, lo que nos lleva a la página de Leopold, que nos pregunta qué queremos.

Desgraciadamente, aun no he conseguido avanzar más allá de este punto. Soy consciente de que las soluciones (menos explicativas) a todos los niveles están en la web, pero si las mirara, esto dejaría de ser un desafío. Si sigo avanzando iré publicando actualizaciones a este post!

No hay comentarios

Python Challenge: Niveles 7-14

Python Challenge es una página con retos a resolver utilizando Python. Esta es la continuación del post con las soluciones de los niveles 0-6 de este challenge. Puedes encontrar el código de las soluciones en Github.

Nivel 7: Smarty

Este nivel nos muestra una imagen con un extraño patrón de tonos de gris. Al leer la intensidad de gris de cada uno de los cuadrados, obtenemos la siguiente serie:

105 110 116 101 103 114 105 116 121

Si transformamos cada uno de estos números en un caracter ASCII, obtenemos la palabra integrity, clave para el siguiente nivel.

Nivel 8: Working hard?

En el código fuente de este nivel observamos un username y un password que están comprimidos mediante bzip2. Usando la librería bz2 de Python, obtenemos el username (huge) y el password (file). Al hacer click en la imagen, nos pide un usuario y una contraseña, que son los que acabamos de averiguar, y nos lleva al siguiente nivel.

Nivel 9: Connect the dots

De nuevo, al observar el código fuente, encontramos dos cadenas, en este caso dos secuencias de números. Tras analizarlas un poco, descubrimos que los números pares son cercanos entre sí y los impares también, en ambas secuencias. Considerando cada secuencia una lista de pares de números, podemos usar el módulo ImageDraw de la librería PIL, para construir una figura que nos dará la clave del siguiente nivel.

Vaca solución al nivel 9 del Python Challenge

Por cierto, si ponemos cow como solución nos dirá que nos hemos equivocado de sexo, una guía muy acertada para no despistar al jugador que lo ha resuelto.

Nivel 10: What are you looking at?

Nos encontramos una imagen, y al hacer click en ella, una secuencia de números. Como es una secuencia de enteros, podemos hacer una búsqueda en OEIS para ver si es conocida, y efectivamente. Es la secuencia Look and Say, que consiste en describir con números el anterior número.

De esta forma, empezamos en 1. El siguiente elemento es lo que vemos en el anterior, que es un uno (11). A continuación, vemos dos unos (21). A continuación, un dos y un uno (1211). Podríamos seguir el nivel manualmente, pero es mejor programarlo, ya que nos pide la longitud del término 30º de la secuencia, que es 5808 cifras.

Nivel 11: Odd even

Observamos una imagen con un efecto extraño, como esas imágenes de Whatsapp que tienen una miniatura y al abrirlas son otra cosa distinta. Fijándonos un poco más vemos que son dos imágenes intercaladas, y al quedarnos con los píxeles con coordenadas impares obtenemos la clave para el siguiente nivel.

Solución al nivel 11 del Python Challenge

Nivel 12: Dealing evil

De nuevo una imagen con un efecto extraño en sus píxeles. Confieso que me llevé bastante tiempo en este nivel. Tras adquirir cierta experiencia con este tipo de retos, sospeché cuando vi que la imagen del nivel se llamaba evil1.jpg, así que probé a poner evil2.jpg y ¡bingo! la imagen nos explica que debemos cambiar la extensión a gfx.

Como curiosidad, al probar evil3.jpg nos topamos con el texto "no more evils...", y al probar evil4.jpg encontramos una imagen que en realidad es un archivo de texto que dice: "Bert is evil! go back!".

Tras mucha desesperación, decidí abrir la imagen con un editor hexadecimal, y me encontré la clave para solucionar el nivel, la famosa etiqueta ÿOÿà que identifica el inicio de un archivo jpeg.

Imagen del nivel 12 abierta con un editor hexadecimal

La etiqueta aparece de forma discontínua varias veces, al igual que la etiqueta GIF8. Si tomamos uno de cada 5 píxeles y lo convertimos en 5 imágenes, obtendremos la clave para el siguiente nivel: disproportional.

Nivel 13: Call him

Observando el código fuente encontramos un enlace a un servidor XML-RPC. Al hacer listMethods() en él, encontramos un único método definido, phone. Ya que la pista del nivel es "phone that evil", y sabemos que Bert es evil por el nivel anterior, llamamos a Bert, y obtenemos la solución del nivel.

A estas alturas, los niveles se complican hasta un nivel bastante poco intuitivo. Perdí muchas horas porque llamar a bert no daba ningún resultado si la B no era mayúscula.

Nivel 14: Walk around

Este nivel es bastante sencillo en comparación con el anterior: nos encontramos una imagen de una ensaimada (en forma de espiral) y abajo, una imagen que al abrirla sólo tiene 1px de altura.

Al enrollarla en forma de espiral, obtenemos la imagen de un gato. Ponemos cat en la URL, y nos enseña el gato, cuyo nombre es Uzi. Ponemos Uzi en la URL, y llegamos al siguiente nivel.

Puedes encontrar la solución a los siguientes niveles en el post con las soluciones de los niveles 15-17.

No hay comentarios

Python Challenge: Niveles 0-6

Python Challenge es una página con retos a resolver utilizando Python. Es posible resolverlos utilizando otros lenguajes, aunque la finalidad del juego es aprender más sobre librerías y funcionalidades específicas de Python.

En este post voy a enseñar las soluciones a los 7 primeros niveles de este Challenge. Conforme siga avanzando, publicaré las soluciones a niveles posteriores. Puedes encontrar el código de las soluciones en Github.

Nivel 0: Warming up

Este es un nivel bastante sencillo, en el que sólo tendrás que calcular la potencia que se muestra en la imagen, y sustituir en la URL el 0 por el valor de esta.

Nivel 1: What about making trans?

De nuevo, un nivel muy sencillo, en el que el propio título de la página nos dice qué hacer. Nos dan un texto cifrado por rotación, y qué rotación tenemos que hacer, usando maketrans para solucionarlo. Al hacerlo, obtenemos este texto:

i hope you didnt translate it by hand. thats what computers are for. doing it in by hand is inefficient and that's why this text is so long. using string.maketrans() is recommended. now apply on the url.

Hacemos el mismo maketrans sobre la URL, y llegamos al siguiente nivel.

Nivel 2: OCR

El propio nivel nos dice que miremos el código fuente. Lo miramos y encontramos dos comentarios, el primero de ellos:

find rare characters in the mess below:

Justo después, encontramos una masa de caracteres sin sentido. Nos quedamos sólo con las letras de la masa, y obtenemos la clave para el siguiente nivel.

Nivel 3: Re

La pista nos sugiere que busquemos una letra minúscula, rodeada de exactamente 3 letras mayúsculas a cada lado. Utilizando expresiones regulares hacemos la búsqueda [^A-Z][A-Z]{3}([a-z])[A-Z]{3}[^A-Z] y encontramos unas cuantas letras, que juntas forman la solución a este nivel.

Nivel 4: Follow the chain

Al hacer click en la imagen, llegamos a una página terminada en ?nothing=12345 con el siguiente texto:

and the next nothing is 44827

Al cambiar el número en la URL, llegamos a otra página igual, que de nuevo apunta a otro número distinto. Parece que podríamos llevarnos así todo el día, por lo que habrá que hacer uso de una librería de peticiones HTTP, como es el caso de urllib (incluida en Python) o requests.

Por medio de la navegación nos encontraremos que hay que dividir entre 2 uno de los códigos. Quitando esto el nivel no tiene mayor complicación, seguimos 250 páginas y llegaremos al enlace al siguiente nivel.

Nivel 5: Peak hell

La pista es que pronunciemos el título del nivel, que suena sospechosamente parecido a Pickle, la librería de serialización de objetos en Python.

En el código fuente encontramos un archivo pickle. Al importarlo y examinarlo un poco, se ve que es una lista de líneas de un texto. Cada línea, en vez de ser una lista de caracteres, es una lista de pares (carácter, repeticiones). Al reconstruir el texto, obtenemos un bonito ASCII art:

ASCII art solución al nivel 5 del Python Challenge

Nivel 6: Now there are pairs

Este problema es bastante parecido al 4. Nos muestran una imagen de una cremallera (zip en inglés), y al cambiar la extensión de la imagen de png a zip, encontramos un archivo comprimido con muchos archivos txt y un readme, que reza:

welcome to my zipped list.
hint1: start from 90052
hint2: answer is inside the zip

Navegamos por los archivos del mismo modo que en el nivel 4, esta vez usando la librería zipfile, hasta llegar al final, que en este caso no es la solución, sino el texto "collect the comments".

Como en los archivos zip existe un campo de comentarios para los archivos, vamos guardando los comentarios de cada uno conforme navegamos. Al juntarlos todos, de nuevo obtenemos un mensaje en ASCII art.

En este caso, el ASCII art está pensado para despistar. La palabra que forma no es relevante, pero sí lo son los caracteres que forman las letras.

Puedes encontrar la solución a los siguientes niveles en el post con las soluciones de los niveles 7-14.

No hay comentarios

< RecientesAntiguas >