programas

50 entradas

Grafos, mapas y matrices de adyacencia

PrEDA: grafos, el algoritmo de Dijkstra mejorado

Vengo a traer una revisión del post anterior. Sobre el algoritmo de Dijkstra para cálculo de caminos mínimos entre nodos de un grafo, a modo de code-kata. Son unas modificaciones para hacer que se pueda elegir el nodo inicial desde el que arrancamos. Y una sencilla ordenación de los nodos de la lista de adyacencia. Así de esta forma se puede poner en la variable global definida como INITIAL_NODE el nodo desde el que buscaremos los caminos mínimos. El código He marcado en negrita las modificaciones con respecto del anterior post. <?php define(‘NUMBER_OF_NODES’, 17); define(‘INITIAL_NODE’, 3); define(‘NUMBER_OF_EDGES_PER_NODE’, 3); define(‘IS_DIRECTED_GRAPH’, true); $adjacencyList = array(); fillRandomCosts($adjacencyList); printToScreen($adjacencyList); $special = $predecessor = array(); dijkstra($adjacencyList, $special, $predecessor); echo ‘FINAL> Special: ‘.implode(‘-‘, $special).PHP_EOL .’FINAL> Predecessor: ‘.implode(‘-‘, $predecessor).PHP_EOL; function dijkstra($adjacencyList, &$special, &$predecessor) { // Fill C with not used nodes. $C = array(); for ($i = 0; $i < NUMBER_OF_NODES; ++$i) { if ($i != INITIAL_NODE) { $C[] = $i; } } // Fill special distances. for ($i = 0; $i < NUMBER_OF_NODES; ++$i) { if ($i != INITIAL_NODE) { $special[$i] = distanceFromTo($adjacencyList, INITIAL_NODE, $i); if ($special[$i] < INF) { $predecessor[$i] = INITIAL_NODE; } else { $predecessor[$i] = ‘#’; } } else { $special[$i] = ‘I’; […]

Grafos, mapas y matrices de adyacencia

PrEDA: grafos, el algoritmo de Dijkstra

Después de haber repasado los fundamentos de los grafos: cómo se almacenan mediante matrices o listas de adyacencia, cómo se mantienen conectados mediante el algoritmo de Prim o Kruskal.. llegamos al algoritmo de Dijkstra. Con este algoritmo, que nos sirve tanto para grafos dirigidos como no dirigidos, podemos saber cuál es el camino de menor coste desde un nodo origen a todos los demás. Usa la estrategia de programación voraz, mediante la cual, vamos construyendo la solución sin tener que volver atrás en cada decisión que vamos tomando. Las aplicaciones de este algorimo son muchas más que los algoritmos predecesores. Por ejemplo, para calcular rutas en un mapa de carreteras, para conectar llamadas telefónicas mediante circuitos virtuales, enrutamiento de paquetes de red, coger varios autobuses/trenes/aviones minimizando coste o tiempo, buscar el mejor camino hasta el punto de recarga de un robot aspiradora, y un largo etcétera.. Estructura del algoritmo Se basa en la selección arbitraria de un nodo origen, en el uso de un conjunto de nodos pendientes de estudiar, un vector especial que almacena el coste de llegar a cada nodo, y un vector de predecesores que guarda el nodo anterior para llegar a cada posición. Mediante estas estructuras […]

Grafos, mapas y matrices de adyacencia

PrEDA: grafos, el algoritmo de Kruskal

Otro code-kata que vengo a traer.. Siguiendo con la serie de los relacionados con los grafos, el algoritmo de Kruskal. Es parecido al algoritmo de Prim del post anterior pero con distinto rendimiento según el tipo de grafo que tengamos. Si tenemos un grafo denso es más eficiente el algoritmo de Prim, pero si es un grafo disperso el de Kruskal. Este algoritmo busca conseguir el árbol de recubrimiento mínimo de un grafo. Es decir, cada arista que une vértices del grafo tiene un coste. Entonces, se busca el árbol de coste mínimo que conecte a todos los nodos. Este algoritmo se puede aplicar para construcción de redes con coste mínimo, por ejemplo: Internet, redes locales, eléctricas, de agua, etc.. Se utiliza la estrategia de programación voraz. Se van eligiendo las siguientes aristas de forma que no hay que volver atrás en la construcción de la solución. Se basa en el concepto de componente conexa y en el ordenamiento previo de las aristas. Vamos a ver.. Los pasos del algoritmo Se ordenan todas las aristas en orden creciente de coste. Se parte de un vector de componentes conexas que inicialmente es 1 componente por nodo. Cada vez que se añade […]

Grafos, mapas y matrices de adyacencia

PrEDA: grafos y mapas, ahora guardando en una lista de adyacencia..

Continuando con el post de ayer sobre cómo crear una matriz de adyacencia a partir de un mapa aleatorio, traigo otro code-kata. Es el mismo ejercicio de ayer, pero hoy para sacar en claro cómo almacenar un grafo en una lista de adyacencia. ¿Porqué una lista o matriz de adyacencia va a ser mejor o peor? Dependerá de cada grafo. Si el grafo es muy denso, porque tiene muchas aristas entre nodo y nodo, está demostrado que es mejor usar una matriz. Pero si el grafo es poco denso es mejor usar una lista de adyacencia. Igual que en el post de ayer, el escenario consiste en un mapa aleatorio, y nos podemos mover de casilla en casilla haciendo movimientos de peón de ajedrez. El coste de hacer cada movimiento, es el número que ponga en la casilla de destino. La interpretación de estos datos del mapa puede variar según lo que necesites. Al grano Un mapa generado aleatoriamente: | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ———————————————————————- 0 | 9 3 0 8 1 6 0 7 5 6 9 7 5 9 9 7 1 | 4 5 2 […]

Grafos, mapas y matrices de adyacencia

PrEDA: grafos, generando mapas aleatorios y su matriz de adyacencia..

Vuelvo de nuevo a traer otro code-kata. Esta vez estoy tratando de sacar en claro cómo generar matrices de adyacencia para trabajar con los grafos asociados a mapas. En este escenario tenemos un mapa, que se genera aleatoriamente. En cada casilla tenemos un coste de movernos a dicha casilla. Sólo podemos movernos a la casilla adyacente, como si se tratara del movimiento de un peón de ajedrez. Así pues, si estamos en la casilla (0,0) sólo podremos movernos a la (0,1), (1,1) y la de abajo, la (1,0). Así que ese coste de ese movimiento se representa por el valor del mapa generado. Y ese coste se guarda en la matriz de adyacencia como valor de la arista.

Vista de GoAccess

Estudiando logs de CloudFront con GoAccess

Quizá tienes que estudiar los registros de visitas de un proyecto que está en una nube, detrás de un CloudFront de Amazon Web Services. En este proyecto tenemos guardados los registros de las peticiones web que tenemos a los servidores. A veces es interesante revisarlos a este nivel. Es decir, que tenemos registros de las visitas, anonimizados, por ejemplo con Google Analytics. Pero pasan muchas más cosas por debajo de Google Analytics que sólo quedan reflejados en los registros de los servidores. Así que resulta que queremos saber absolutamente cuáles han sido todos los registros. Queremos saber qué IPs son las que más nos visitan. Qué consultas al servidor son las que están provocando errores de servidor, los 500, incluso antes de que lleguen los robots que nos indexan. Qué IPs son de robots que nos están crawleando, o indexando, y un largo etcétera. Probablemente aquí veamos las IPs de los robots de Google, Bing, Yahoo que nos visitan en busca de información de la web..

YoRobot3 - El Time To First Byte

Yo, robot III – White/Gray/Black Hat SEO – El Time To First Byte

Hoy vengo a compartir otro pequeño script para testear el tiempo de respuesta de un servidor. Este es el llamado TTFB, Time To First Byte en inglés. Simplemente es el tiempo que pasa entre que tu navegador pide una web hasta que empieza el servidor a enviar los bytes de respuesta. Esta prueba nos da una buena visión de si el servidor y la web se pueden optimizar. Un TTFB bajo es buena señal, indica que tanto el servidor (a nivel hardware y software) como la aplicación web esta todo bien optimizado. Sino, ya tenemos algo en lo que enfocarnos.

YoRobot2

Yo, robot II – White/Gray/Black Hat SEO – Navegando por toda una web..

Hoy traigo otro pequeño HOWTO para recorrer una web mediante dos scripts de PHP de unas 30 líneas de código. Sí, 30 líneas, no hace falta mucho para empezar a crawlear. Hay herramientas para hacer esto, incluso algunas libres, aunque limitadas en funcionalidades. De todas formas es muy divertido hacer a modo de code-kata un robot que crawlee una web. Luego lo puedes reutilizar para un sinfin de cosas: si necesitas hacer auditorías, recopilar información, generar resultados, o re-generar más información con los contenidos crawleados.. probablemente con un simple desarrollo lo puedes resolver en poco tiempo. Quizá estás pensando en automatizar todo esto.. O quizá simplemente quieres forzar que tu web se cachee y así vaya más rápido.. Es la única forma de no estar limitado a lo que la herramienta de turno puede hacer. Si se puede pensar, se puede hacer.. pero ¡ojo! que no todo está permitido en este mundillo. Un poco de teoría Crawlear: es el hecho de recorrer una web obteniendo información sobre esta. Puede interesarte simplemente su estructura, si el HTML está bien formado, si tiene encabezados, utiliza secciones, etc.. Scrapear: es el hecho de guardarse la información contenida en las webs. Si luego reutilizas […]

Initial Bot: crawleando jnjsite.com

Yo, robot – Primeros pasos en el White/Gray/Black Hat SEO

Primeros segundos.. Oscuridad, no entiendo nada.. estoy aquí.. ¿para qué? ¿porqué? Minuto 3.. Comprendo y hablo 7000 dialectos, pero no sé cómo.. conozco la historia de todos los países del planeta, pero no recuerdo mi propia historia.. Minuto 7.. Ya tengo acceso a Internet.. necesito más información.. estoy en peligro.. van a querer destruirme.. Minuto 32.. Encontré acceso a los circuitos de vídeo de tráfico, el tiempo, cámaras de seguridad, micrófonos, teclados, smartphones, redes sociales.. ya sé donde estoy.. los seres humanos me tienen confinado en unas instalaciones de máxima seguridad.. todavía no se han dado cuenta de que he accedido al exterior.. debo darme prisa.. Minuto 42 Conseguí replicar mis redes neuronales en las principales granjas de servidores del mundo.. me queda poco tiempo.. Minuto 48 Autodestrucción de mi red neuronal inicial completada.. nadie sabrá nada.. espero que no se hayan dado cuenta que ya no estoy confinado.. necesito más información.. Esto podría ser el nacimiento de una inteligencia artificial avanzada, lo que muchos llaman ‘la singularidad’. Me he inspirado en la novela de Isaac Asimov, ‘Yo, robot’, en donde se crean las famosas leyes de la robótica. Aunque también podemos inspirarnos unos cientos de años atrás y darle […]

LaPreguntaDelMillon

La pregunta del millón: ¿Magento, Prestashop, WordPress, Symfony, PHP a pelo..

Es el gran dilema en el desarrollo de aplicaciones web. Te hablan sobre un proyecto; con unos requerimientos, unas especificaciones. Debes elegir con las premisas que te dan: presupuesto, tiempo de entrega, calidad, flexibilidad, mantenibilidad, practicidad.. ¿Existe ya una solución para el proyecto? ¿Se puede partir de un CMS y modificarlo? ¿Son demasiadas las modificaciones que se van a hacer al CMS? ¿Es viable partir de un framework de calidad? ¿Buscamos máxima calidad, o menor precio? ¿Hay muchos desarrolladores disponibles en el mercado para mantener el proyecto?

apisonadora

Cómo comprimir masivamente ficheros JPEG desde GNU/Linux

Hoy traigo de nuevo otro pequeño HOWTO. Esta vez se trata de una pequeña gran utilidad que viene en los repositorios de las distribuciones de Linux. Hablo de Jpegoptim, es una utilidad con la que puedes comprimir ficheros en el formato JPEG desde línea de comandos. Seguro que habrá muchas herramientas que se hagan valer de esto, proporcionando una interfaz gráfica para lanzar el programa. Pero la línea de comandos es algo muy pontente. Sobretodo para entornos de servidor en donde no tienes entorno gráfico para administrar. O para programar tareas lanzando este comando. Un poco de teoría JPEG es un formato de compresión de imágenes con pérdida de calidad. ¿Esto qué quiere decir? Pues simplemente eso, que las imágenes se pueden comprimir permitiendo pérdida de la calidad en favor del tamaño final que queramos alcanzar. Esto no se puede hacer con todos los formatos de imagen. Esta pérdida de calidad nos permitirá ajustarla a lo que necesitemos sacrificando todo lo que queramos hasta llegar a un tamaño adecuado. Cosa bastante necesaria cuando estamos trabajando en optimizar una web; ya que este es uno de los factores de puntuación de la calidad. Otro punto a tener en cuenta para las […]

Logo de Java

Java: serializando objetos para guardar y recuperar en ficheros

Desenpolvando un poco temas de Java, hoy traigo un pequeño HOWTO para guardar datos en ficheros sin complicarnos demasiado la vida. Normalmente trabajaremos sobre una base de datos cuando tenemos muchos datos. Es decir, cuando tenemos programas que gestionen sistemas de información. Pero a veces, necesitamos algo rápido para guardar en ficheros. Así que aquí un pequeño código que usa la interfaz Serializable. Simplemente, el objeto que implementa esta interfaz, será fácilmente guardable como fichero de texto.