Neutralidad en la red

Hace unos meses contraté la línea de móvil con Vodafone/Ono, con un contrato que ofrecía la tarifa Zero Rating. Básicamente, consistía en no contar en el consumo de datos algunas aplicaciones de mensajería: Telegram, Line, Whatsapp, y algunas más.

En su momento me pareció muy buena idea, podría usar los bots de Telegram para no consumir datos al descargar vídeos de YouTube, canciones, o convertir archivos a otro formato. Y no me di cuenta de la cara oculta de esta tarifa.

Supongamos que mañana diseño un nuevo servicio de mensajería, con muchas funcionalidades, tan bueno que merecería estar en el top de aplicaciones descargadas. Un gran número de usuarios no lo descargarán, simplemente porque con otras alternativas no consumen datos.

Y puede ir a más. Eligiendo qué aplicaciones tienen permitido hacer tal cosa y qué otras no, estamos abriendo la veda a estrategias como la de MEO en Portugal.

Oferta de MEO con paquetes separados por apps y webs

Gran parte de la belleza de Internet reside en su neutralidad. Para que podáis estar leyendo mi web, los bytes van desde mi servidor doméstico hasta vosotros siguiendo el mismo camino que seguirían al usar Google o Facebook. Sin embargo, al matar la neutralidad en la red, se está permitiendo la creación de autopistas de peaje, vías rápidas que obligan a las webs a pagar cierta cantidad a las operadoras para poder funcionar a la máxima velocidad.

Estas prácticas están prohibidas en la Unión Europea, aunque en España la interpretación ha sido bastante laxa. Seguramente os suenen casos de operadoras que bajan la velocidad a usuarios que utilizan descargas P2P o VoIP, o que directamente las bloquean.

Esta semana en EEUU se está decidiendo algo parecido. Muchos usuarios están haciendo todo lo posible por evitar que la nueva ley entre en vigor. Y allí las acciones de algunas operadoras han sido bastante más malignas. Por ejemplo, AT&T censuró un directo de Pearl Jam por las críticas de su cantante al en aquel entonces presidente George Bush.

En definitiva, podemos decir que estamos mejor que la mayoría, aunque podríamos estar mejor. Y siendo prácticos, existe otra neutralidad en la red que merece más nuestra atención, la App Neutrality: Google y Apple comparten un duopolio que les da potestad absoluta para decidir incluir o no incluir ciertas aplicaciones en sus stores, y colocarlas en una posición más alta o más baja en el ranking.

Y también podríamos hablar de la Search neutrality, aunque eso da para otro post.

2 comentarios

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

< RecientesAntiguas >