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.

¿Por qué tener un blog? ¿Sirve para algo?

Últimamente he pensado mucho sobre los blogs. He quitado los anuncios del mío. He preguntado y leído mucho, sobre SEO, branding, SEM, mailing, redes sociales, etc.. para buscar la respuesta a si debemos mantener un blog. Qué relación hay entre todos los canales de entrada a tu negocio de Internet. Así que, aquí estoy de nuevo escribiendo los resultados de esta experiencia. La pregunta que se hace mucha gente es.. ¿Por qué mantener un blog? Esta pregunta te puede derivar a varias relacionadas como.. ¿En qué me beneficia tener un blog? ¿Me beneficia? ¿A mi empresa le interesa tener un blog? ¿Me interesa tener un blog personal? En este post pretendo sumergirte, poco a poco, en el océano del marketing online. Sumergirte en el rendimiento que se puede tener de un blog, en la rentabilidad que puede haber después de invertir tiempo y esfuerzo en un blog. Si te preguntas sobre todo esto, y todavía piensas que un blog no te puede beneficiar económicamente, lee y no cometas este brutal error.

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..

Números

PrEDA: el algoritmo de ordenamiento Mergesort

De nuevo con otro code-kata ya estoy por aquí de nuevo. Se trata ahora de un algoritmo más sencillo que los anteriores. El Heapsort se apoya en montículos para su ordenamiento. El Quicksort hace un pivotaje algo complejo para hacer la división del vector en dos más simples. En este caso, el Mergesort, hace un ordenamiento más simple. Mergesort aplica la estrategia de divide y vencerás para hacer el ordenamiento. Con esto, tenemos que un vector de números desordenado se divide en dos. Estos dos subvectores se ordenan por separado usando Mergesort recursivamente. Y al tenerlos ordenados, se fusionan en un vector final cogiendo elementos de uno u otro vector en orden creciente.

Números

PrEDA: el algoritmo de ordenamiento Heapsort

De nuevo traigo a modo de code-kata otro algoritmo de programación. En este caso no se usa ninguna técnica avanzada de programación. Sino que simplemente se usa el algoritmo de ordenamiento Heapsort, que como su nombre indica, se sirve de un heap (montículo) para hacer el ordenamiento. Como ya hablé en este otro post sobre los montículos, he reutilizado el código para hacer un par de clases genéricas que nos pueden servir para construir algoritmos más avanzados. PHP ya nos provee de una clase que implementa un montículo, el SplHeap. También tenemos en PHP una clase para un SplMinHeap y SplMaxHeap. Pero no podemos controlar cómo hacemos la valoración de mínimo o máximo para poner arriba del montículo los objetos ordenados. Así que no queda más remedio que extender la clase que nos provee PHP.

Números

PrEDA: el algoritmo de ordenamiento Quicksort

Vuelvo a la carga con los algoritmos de programación. Hoy traigo a modo de code-kata el algoritmo de ordenamiento Quicksort. En este algoritmo se utiliza la estrategia de programación divide y vencerás. Aplicándola, vamos dividiendo un vector inicial no ordenado, en subvectores que vamos a dividir una y otra vez recursivamente, hasta tener todos los elementos ordenados. Antes de dividir un vector en dos subvectores se aplica una técnica de pivotaje. Con este pivotaje de los elementos, obtendremos el vector dividido en 2 partes, más un elemento central llamado pivote. Este elemento pivote hará que en la parte izquierda del vector todos los elementos sean menores que el pivote. Y a su vez, en la parte derecha, todos los elementos serán mayores que el pivote.

GNU/Linux

Servidor GNU/Linux bloqueado, no responde, no actualiza, no da servicio

Si has puesto un servidor Ubuntu/Linux lanzándole actualizaciones automáticas puede que hayas llegado a encontrarlo bloqueado. El servidor ha dejado de actualizarse y no hay manera de encontrar el problema. Cuesta mucho entrar al servidor. Un reinicio, paramos servicios, podemos hacer un par de cosas recién conectados, pero vuelve a bloquearse.. Volvemos a reiniciar para volver a entrar corriendo a ver qué pasa.. la gente corre.. ¡las mujeres y los niños primero! 😀 Esto pueden ser los síntomas de un servidor lleno. Lleno el disco duro, la memoria RAM, los i-nodos.. ha empezado a reventar por todos lados y necesitamos volverlo a la normalidad. Toca pues hacer un par de cosas..

WP actualizando a PHP7

Pon tu WordPress a un 600% de velocidad con PHP7

Siempre andamos hablando con los compañeros de trabajo que si es mejor que la web vaya rápido. Que si no hay que instalar muchos plugins en WordPress. Que no hay que meter demasiadas florituras en la web. Que lo más importante es el contenido. Y un largo etcétera.. Llegados a este punto, llegó el momento de actualizarnos en PHP. Tenía en el servidor PHP5 y ya conocía las bondades de PHP7. Pero también sé de los problemas que hay en los CMSs para ser compatibles con PHP7. Así que prueba tras prueba, he hecho una limpieza total de esta web y aquí traigo los resultados. Y aprovechando tantos cambios, también un cambio de diseño 🙂

Redirecciones HTTP

Cómo hacer un sencillo fichero de redirecciones con .htaccess

Una de las tareas habituales en las webs es hacer redirecciones. Las principales redirecciones que podemos necesitar son las temporales o las permanentes. Los principales códigos de respuesta de redirección van desde el 300 al 308, pero los más habituales son los 301 y el 302. Así de esta forma, si queremos hacer una redirección temporal se recomienda usar una redirección de tipo 302. En el caso de que ya sea una redirección definitiva conviene hacer una redirección definitiva de tipo 301. Los código 308 y 307 se corresponden respectivamente a los 301 y 302 pero con distintos matices. Estas redirecciones podemos almacenarlas sin más complicaciones en el fichero .htaccess en el directorio raiz.

Heap min max montículos

PrEDA: cómo programar montículos mínimos o máximos de cualquier tipo de objetos

Una de las mejores formas de ordenar objetos es haciendo montículos. Está demostrado matemáticamente cómo mejoran la eficiencia de muchos tipos de algoritmos. Así que aquí traigo a modo de code-kata, de nuevo, otro pequeño script con el que se puede implementar montículos mínimos o máximos de cualquier tipo de objetos. Un montículo es un tipo especial de árbol binario. Son binarios porque cada nodo tiene de máximo dos hijos. Además, éstos árboles están ordenados de arriba a abajo. Si es un montículo de mínimos entonces los elementos de arriba, los padres, siempre tienen un valor menor que los hijos. Si por el contrario es un montículo de máximos, entonces los elementos de arriba, los padres tienen un valor mayor. De esta forma nos aseguramos que siempre tengamos el elemento mayor o menor en el nodo raiz del árbol. Esto es muy útil para utilizarlos en todo tipo de algoritmos de programación. Punto de partida En PHP tenemos una clase, que implementa mediante un vector interno, un montículo. Se trata de la clase SplHeap. Entonces simplemente tenemos que hacer herencia de SplHeap extendiendo la clase SplHeap. El código es bien sencillo: <?php define(‘NUMBER_OF_NODES’, 30); class TNodo { public $cost; public […]

Gantt

PrEDA: priorizando tareas para obtener el máximo de beneficio

Hoy traigo a modo de code-kata otro problema resuelto. Se trata de resolver un problema muy muy común en informática, la gestión de tareas. En este caso, se trata de aplicar la gestión de tareas, o proyectos, con la condición de obtener el máximo de beneficio. Podríamos gestionar las tareas minimizando el tiempo en el sistema, distribuyendo tareas entre varios agentes.. O podríamos aplicarlo a otros ámbitos como la cosecha de cultivos, en donde habría que priorizar en función al tiempo de putrefacción y beneficio, teniendo en cuenta el tiempo necesario para cada cosecha. Es decir, en este caso, se trata de obtener el orden óptimo de tareas de forma que se maximize el beneficio. Tenemos entonces una duración de cada tarea, un beneficio, y un tiempo de entrega. Para resolver este problema, la mejor estrategia es la ramificación y poda. No existe una estrategia voraz, ni de divide y vencerás que podamos usar. Tampoco la vuelta atrás es la mejor solución, porque se trata de obtener la solución óptima en el menor tiempo posible. Entonces, tendremos que generar un árbol de posibilidades, un árbol de combinación de tareas. De forma que mientras que generamos el árbol tenemos que tener […]