Algoritmo Quick Union

Algoritmo Quick Union
Al igual que Quick Find. El algoritmo Quick Union permite conectar nodos de un Árbol entre sí, la diferencia es que en Quick Find las referencias son con el nodo raíz, y Quick Union mantiene una referencia al nodo padre.

Quick Union
El algoritmo se basa en 3 funciones principales, una para encontrar el nodo raíz, otra para unir 2 nodos y una función para verificar si existe conexión entre 2 nodos. Toda la información sobre las conexiones entre nodos se almacenan en un arreglo.

Encontrar el nodo raíz
Para encontrar el nodo raíz basta con recorrer el arreglo dentro de un ciclo hasta que el valor del arreglo[i] sea igual al índice, lo cual quiere decir que alcanzamos la raíz, el algoritmo es de complejidad O(n) donde n = longitud necesaria para alcanzar la raíz, en pseudocódigo:

def find_root(int []array, int node):
    i = node
    while(array[i] != i):
        i = array[i]
    return i

Unir 2 nodos
Para unir 2 nodos "a y b" hay que establecer el nodo raíz de "b" en "a", es decir, hacer algo como:

def union(int []array, int node1, int node2):
    array[find_root(node1)] = find_root(node2)

Saber si 2 nodos están conectados
Sería verificar si los nodos tienen la misma raíz, la complejidad es O(n) al igual que la unión:

Algoritmo Quick Find

El curso de coursera “Algorithms, Part I” me vino excelente ya que este año quería mejorar mis conocimientos en algoritmos. El curso es totalmente gratuito y los vídeos son de altísimo nivel, muy recomendado.

La primera semana introduce un par de algoritmos de conectividad dinámica, son Quick Find y Quick Union. Estos algoritmos permiten conectar y verificar la conexión que existe entre nodos de una estructura de tipo Árbol, representada en un Array. Primero escribiré sobre Quick Find y en otro post sobre Quick Union, para no hacer los posts tan largos.

Quick Find

El algoritmo se basa en 2 funciones principales, Union y Find, Union permite conectar 2 nodos y Find permite verificar si dos nodos están conectados, directa o indirectamente, es decir a través de otros nodos.

Union

La unión permite conectar 2 nodos, la lógica es simple (complejidad O(n)), se basa en recorrer todo el arreglo dentro de un ciclo y establecer como raíz al nodo2 en todos los nodos que tengan como raíz al nodo1, para ello basta con verificar en cada paso si arreglo[i] == arreglo[nodo1], de ser verdadero, sustituir arreglo[i] con el valor del arreglo[nodo2]. De manera tal que todos tengan el mismo nodo raíz, en Pseudopython sería:

def union(int []array, int node1, int node2):
    temp = array[node1]
    for i to len(array):
        if array[i] == temp:
            array[i] = array[node2]

Find

Con find se verifica si dos nodos están conectados y es una operación muy rápida, O(1), creo que por eso el nombre del algoritmo “Quick Find”, basta con verificar si los nodos tienen comparten la misma raíz arreglo[nodo1]==arreglo[nodo2]

 
  Imagen tomada de uno de los vídeos del curso en Coursera

Por ejemplo, en la imagen los nodos 0 5 y 6 están conectados. En el arreglo el valor en la posición id[0] id[5] e id[6] es 0 ya que el id 0 es algo así como el nodo raíz y la forma de verificar si están conectados es que todos tengan el mismo valor.

Crear nuestros propios eventos en Node.js

Un evento, en el contexto de programación y código, es un suceso de interés al cual nos podemos suscribir y realizar alguna acción en específico, por ejemplo: En el navegador con JavaScript tenemos la función setInterval(callback, interval); que dispara un evento al callback cada vez que se cumple el intervalo especificado.

En Node.js son muy utilizados por el API y de cierta manera encajan perfectamente con su naturaleza asíncrona, por ejemplo, hay un evento muy interesante del objeto “process” que se dispara al momento de salir del entorno de ejecución de Node.js, el evento se llama “exit” y podemos suscribirnos de la siguiente manera:

process.on(“exit”, function () {
     console.log(“Saliendo!”);
});

La mayoría del API de Node.js utiliza los eventos para informar cosas interesantes a las cuales podemos suscribirnos y esto es posible gracias al objeto EventEmitter del módulo events, el cual mediante el método emit permite disparar eventos a todos los suscriptores. Haz clic aquí para más información sobre este objeto. Sin duda alguna, los eventos son un paradigma muy interesante, ahora bien, si queremos que nuestros propios objetos generen eventos el proceso es muy sencillo, basta con “heredar” de la clase EventEmitter, mediante el método del módulo util “inherits” y luego disparar el evento mediante “emit”. Veamos un ejemplo sencillo de un objeto llamado Auto el cual emite el evento “arrancar”:

var EventEmitter = require("events").EventEmitter;
var util = require("util");

//Heredar del objeto EventEmitter
util.inherits(Car, EventEmitter);

function Car(brand) {
    EventEmitter.call(this);
    this._brand = brand;
}

Car.prototype.start = function() {
    console.log("Arrancando el auto de marca " + this._brand);
    var date = new Date();
    this.emit("arrancar", date);
}

var car = new Car("Audi");

car.on("arrancar", function(date) {
    console.log("El auto arranca en la fecha: " + date.toString());
});

car.start();

Como vemos, es muy sencillo primero “Heredamos” del objeto EventEmitter, luego disparamos el evento deseado con el método emit, podemos pasar los parámetros que se requieran al suscriptor como argumentos del método emit, en el caso del ejemplo se pasa la fecha de arranque del auto, por último nos suscribimos al evento con el método on.

Referencias:

https://nodejs.org/api/events.html

Configurar PHPUnit y Netbeans en Windows 8

Hace algunos días migré a Windows 8 y tuve que reinstalar todo el entorno de programación desde cero!, me dispuse a descargar todas las herramientas de programación con PHP que usaba en Windows 7, Xampp, Netbeans, etc. Para mi sorpresa las cosas no fueron tan fáciles como esperaba. En este artículo trato de describir como logré la instalación que tenía en Windows 7. La versión usada es Netbeans 7.2 en español.

Instalar Xampp

1) Descargar e instalar xampp para Windows de: http://www.apachefriends.org/en/xampp-windows.html

Es conveniente dejar el path de instalación por defecto, es decir, "C:\xampp". Xampp añade automáticamente el path de php, C:\xampp\php, a las Variables de entorno, por lo que tendremos acceso global desde la terminal a php, y a los paquetes que instalemos con PEAR, como PHPUnit.

2) Luego de instalación ir al directorio de instalación de PHP en Xampp por defecto C:\xampp\php y Eliminar los siguientes archivos:

pear.bat

peardev.bat

phpunit

phpunit.bat