domingo, 9 de diciembre de 2012

Representación interna de un flotante

En este post vamos a hacer un pequeño experimento para desplegar la representación de un flotante, ya que a final de cuentas debe ser guardado como un conjunto de bits.

Primero, repasemos rápidamente uniones en C. En una unión todos sus miembros comparten la misma ubicación de memoria. Por ejemplo, en el siguiente programa, la unión contiene dos elementos, una estructura con cuatro enteros y un arreglo de cuatro enteros. Observen como inicializamos los valores de la estructura y posteriormente desplegamos esos valores usando los miembros del arreglo.

#include <stdio.h>

typedef struct {
  int byte1;
  int byte2;
  int byte3;
  int byte4;
} Mi_estructura;

typedef union {
  Mi_estructura estructura;
  int arreglo[4];
} Mi_union;

void main(void) {
  Mi_union u;
  int i;
  
  u.estructura.byte1 = 11;
  u.estructura.byte2 = 22;
  u.estructura.byte3 = 33;
  u.estructura.byte4 = 44;
  
  for(i = 0; i < 4; i++) {
    printf("%d\n",u.arreglo[i]);
  }
}

Este caso en específico puede ser útil cuando algunas partes del programa son más legibles usando los miembros de la estructura, por ejemplo al momento de asignar valores. Y otras veces es más eficiente usar un arreglo, como al querer copiar o desplegar los elementos.

Regresando al caso de un flotante. Usaremos una unión que contiene un float y un int, en la máquina que estoy usando ambos usan 4 bytes. Lo que haremos es modificar la unión usando el float y desplegar el contenido usando el int.

#include <stdio.h>

typedef union {
  int i;
  float f;
} Mi_union;

void main(void) {
  Mi_union u;
  printf("# bytes int: %zu\n",sizeof(int));
  printf("# bytes float: %zu\n",sizeof(float));
  
  u.f = 1234.5678f;
  printf("%.10f\n",u.f);
  printf("0x%x\n",u.i);
}

Podemos ver en la imagen anterior que el valor 1234.5678f es almacenado con el siguiente patrón de bits 0x449a522b. Este patrón sigue el estándar IEEE754, la siguiente página contiene una muy buena explicación.

Lo que haremos es extraer los bits de acuerdo a este formato y verificaremos que tengamos el valor 1234.5678f.

#include <stdio.h>

typedef union {
  unsigned int i;
  float f;
} Mi_union;

unsigned int extraer_bits(unsigned int valor, short inicio, 
                          short nbits);
void representacion_float(unsigned int valor);

void main(void) {
  Mi_union u;
  printf("# bytes int: %zu\n",sizeof(int));
  printf("# bytes float: %zu\n",sizeof(float));
  
  u.f = 1234.5678f;
  printf("%.10f\n",u.f);
  printf("0x%x\n",u.i);
  representacion_float(u.i);
}


void representacion_float(unsigned int valor){
  unsigned int signo = 0;
  unsigned int exponente_bias = 0;
  unsigned int exponente_unbias = 0;
  unsigned int mantisa = 0;
  unsigned int parte_entera = 0;
  unsigned int parte_decimal = 0;
  unsigned int parte_decimal_max = 0;
  
  signo = extraer_bits(valor, 31, 1);
  exponente_bias = extraer_bits(valor, 23, 8);
  exponente_unbias = exponente_bias - 127;
  mantisa = extraer_bits(valor, 0, 23);
  parte_decimal = extraer_bits(valor,0,23-exponente_unbias);
  parte_decimal_max = 1<<23-exponente_unbias;
  parte_entera = extraer_bits(valor,23-exponente_unbias,
                              exponente_unbias);
  // la parte entera tiene un bit 1 por default al inicio.
  parte_entera |= 1<<exponente_unbias;
  
  printf("Signo: %d\n", signo);
  printf("Exponente (bias): 0x%x (%d)\n", exponente_bias, 
                                          exponente_bias);
  printf("Exponente (unbias): %d\n", exponente_unbias);
  printf("Mantisa: 0x%x\n", mantisa);
  printf("Parte entera: 0x%x (%d)\n", parte_entera, 
                                      parte_entera);
  printf("Parte fraccional: 0x%x (%d) de 0x%x (%d)\n", 
    parte_decimal, parte_decimal, 
    parte_decimal_max, parte_decimal_max);
}


unsigned int extraer_bits(unsigned int valor, short inicio, 
                 short nbits){
  unsigned int mascara = 0;
  short i = 0;
  // primero recorremos el bit inicial al bit 0
  valor >>= inicio;
  // obtener mascara de los bits que deseamos
  for(i = 0; i < nbits; i++){
    mascara <<= 1;
    mascara |= 1;
  }
  // enmascaramos los bits que deseamos
  return valor & mascara;
}

Noten que el código no es muy robusto, ya que para números muy grandes (es decir, exponentes muy grandes) no funciona. Pero ayuda a ilustrar la representación de un flotante.

El programa obtiene los bits correspondientes al signo, el exponente y la mantisa. Además usa el exponente para extraer de la mantisa la parte entera y fraccionaria. La parte fraccionaria la podemos interpretar ya sea viendo los bit y calculando el valor. Por ejemplo, 0x122b en binario es 1 0010 0010 1011, lo cual lo podemos evaluar como 2^−1+2^−4+2^−8+2^−10+2^−12+2^−13 = 0.567749023. Otra forma de verlo, es que el máximo valor de la parte fraccionaria más uno es 0x2000 ó 8192 decimal (es decir esto equivale al valor 1). Por lo que nuestra parte fraccionaria es 4651/8192=0.567749023. Noten, que el valor que obtuvimos es ligeramente menor al valor inicial, esto es a lo que llamamos errores de precisión.

Espero que les haya resultado interesante ver de una forma práctica como guardamos número flotantes.

domingo, 2 de diciembre de 2012

Reiniciar peticiones de tweets

Tutorial de Grafos
Anterior        Índice        Siguiente

En este post volveremos a visitar el programa que obtiene la información de los hash tags. Agregué dos nuevas funcionalidades.

La primera mejora tiene que ver con qué pasa si queremos volver a ejecutar búsquedas y guárdalas en la misma carpeta de tweets de una ejecución anterior. Sin ninguna modificación al programa, lo que pasaría es que los nuevos archivos de salida se agregan sin problema aún cuando volvamos a visitar un mismo hash tag, ya que el nombre del archivo esta formado por un “timestamp” y el hash tag (por ejemplo: 1351987950#felicidad). Y tal vez ese sea un comportamiento deseado.

Sin embargo, decidí modificar el programa para evitar visitar hash tags que hayan sido visitados en ejecuciones anteriores. Esto es muy sencillo, ya que el nombre del archivo contiene el hash tag, por lo que sólo tuve que extraerlos y agregarlos al conjunto de hash tags visitados.

Un efecto secundario de este cambio es cuando nuestro hash tag inicial ya lo habíamos visitado anteriormente, el resultado es que el programa termina inmediatamente. Esto nos lleva a el segundo cambio, inicializar automáticamente la búsqueda cuando pasemos “##” como hash tag inicial en la línea de comandos.

En caso de que hayamos ejecutado el programa previamente, entonces tendremos un conjunto de archivos de los hash tags visitados. Los hash tags dentro de los archivos no necesariamente han sido visitados, por lo que inicializaré los hash tags a visitar con todos aquellos hash tags que no se visitaron en ejecuciones anteriores. El siguiente comando visitará otros 2,000 hash tags, tomando como base la información en "../tweets" de los hash tags visitados anteriormente.

python twitter_search.py "##" 100 5 2000 ../tweets

El código lo pueden encontrar en la siguiente liga.

Creo que por el momento el programa de extracción de datos está bastante completo, en el siguiente post veremos cómo construir nuestro grafo de hash tags con esta información.

Tutorial de Grafos
Anterior        Índice        Siguiente

viernes, 23 de noviembre de 2012

Grafo de hash tags (parte 3)

Tutorial de Grafos
Anterior        Índice        Siguiente

Hasta el momento podemos obtener un número de tweets deseados para un hash tag. El objetivo es obtener la relación entre hash tags. El programa de este post, analiza cada tweet y extrae los hash tags para poder construir más búsquedas. De esta forma podemos obtener más tweets de otros tópicos.

Al mismo tiempo de obtener tweets y extraer hash tags, iremos guardando la información. Usaremos la siguiente convención para guardar los datos. Por cada hash tag que consultemos crearemos un archivo, cuyo nombre es el resultado de concatenar un “timestamp” con el hash tag. El archivo contiene un hash tag por línea, estos son los hash tags encontrados en los tweets que regreso la búsqueda. Por ejemplo, después de consultar #Mexico, obtuvimos el siguiente archivo:

Nombre del archivo: 1351385380#mexico

Contenido del archivo:

#musica 
#cancun 
#guadalajara 
...
#instagram 
#instagramhub 
...
#saltillo 
#torreon 
...
#saltillo 
#argentina 
#colombia 
#bolivia 
#brasil 
...
#reforma 
#instagram
...

Como pueden ver, algunos hash tags aparecen más de una vez; esto se debe a que el mismo hash tag está en varios tweets. Decidí dejar los duplicados ya que considero que son un muy buen indicador de qué tan relacionados están los tópicos.

Esta versión del programa recibe cinco parámetros, por ejemplo:

python twitter_search.py "#Mexico" 50 5 500 ./tweets
  1. El hash tag inicial, es decir, con el que iniciaremos las búsquedas.
  2. El número de resultados por petición. En este ejemplo cada petición a Twitter regresará a lo más 50 tweets.
  3. El número de peticiones por hash tag. En el ejemplo, para cada hash tag que busquemos realizaremos a los más 5 peticiones. Este parámetro junto con el anterior nos da el máximo número de tweets por hash tag. En este caso a lo más 250 tweets por hash tag. Puede ser menor, ya que algunos tópicos son poco populares.
  4. El número de hash tags a visitar. Por ejemplo, buscaremos 500 hash tags.
  5. El directorio donde queremos guardar los resultados. Después de que se termine de ejecutar el comando anterior, tendremos 500 archivos en el directorio ./tweets

La lógica del programa es la siguiente:

Mientras no hayamos visitado el número de hash tags

  1. Obtener los tweets de un hash tag que aún no hayamos visitado.
  2. Extraer los hash tags de los tweets.
  3. Guardar los hash tags asociados al hash tag consultado.
  4. Actualizar la información de los hash tags a visitar con los hash tags obtenidos en el paso 2. En este paso sólo agregamos hash tags que no hayamos visitado y que no estén ya en la lista por visitar.

El código lo pueden encontrar en la siguiente liga.

Tutorial de Grafos
Anterior        Índice        Siguiente

domingo, 18 de noviembre de 2012

Grafo de hash tags (parte 2)

Tutorial de Grafos
Anterior        Índice        Siguiente

Ahora modificaremos el programa del post anterior para obtener más de 15 tweets; que es lo que regresa una petición sin parámetros. El programa recibe dos parámetros, además del hash tag inicial, también espera el número de tweets que se desean obtener. Por ejemplo:

python twitter_search.py "#Toluca" 35

Obtiene 35 tweets que contienen el hash tag #Toluca. El programa realiza peticiones hasta que obtiene los tweets deseados.

Sin embargo hay un punto a considerar, la documentación de Twitter menciona que para la API de búsqueda existe un límite en la frecuencia con la que se pueden realizar peticiones, pero no publican dicho límite. En caso de que excedamos este límite simplemente obtendremos algo como:

{"error":"..."}

Por lo que antes de iniciar una nueva petición, espero 5 segundos, si la petición resulta en un error, espero el doble. Quizá tengamos que modificar estos valores.

El siguiente es un ejemplo de la salida del programa.

El código lo pueden encontrar aquí. En el siguiente post comenzaremos a navegar entre hash tags.

Tutorial de Grafos
Anterior        Índice        Siguiente

sábado, 3 de noviembre de 2012

Grafo de hash tags (parte 1)

Tutorial de Grafos
Índice        Siguiente

Realizar una búsqueda usando la API de twitter es tan sencillo como construir la siguiente URL:

http://search.twitter.com/search.json?q=%23Toluca

Esta consulta regresa tweets recientes que contienen el hash tag #Toluca. De hecho si pegan esta URL en su navegado pueden observar el formato de la respuesta. La respuesta viene en formato JSON. Los signos de llaves indican un objeto y los corchetes indican un arreglo.

{
 "completed_in":0.089,
 "max_id":259679677768151040,
 "max_id_str":"259679677768151040",
 "next_page":"?page=2&max_id=259679677768151040&q=%23Toluca",
 "page":1,
 "query":"%23Toluca",
 "refresh_url":"?since_id=259679677768151040&q=%23Toluca",
 "results":
  [
   {
    "created_at":"Sat, 20 Oct 2012 15:18:54 +0000",
    "from_user":"tlcweather",
    "from_user_id":461072765,
    "from_user_id_str":"461072765",
    "from_user_name":"Toluca Weather",
    "geo":null,
    "id":259675063110995968,
    "id_str":"259675063110995968",
    "iso_language_code":"es",
    "metadata":{"result_type":"recent"},
    "profile_image_url":"http:\/\/a0.twimg.com\/profile_...",
    "profile_image_url_https":"https:\/\/si0.twimg.com\/...",
    "source":"<a href="http:\/\/www.google.com\/">Google<\/a>",
    "text":"Toluca, MEXICO Weather :: 13C Mist ... #Toluca #Mexico",
    "to_user":null,
    "to_user_id":0,
    "to_user_id_str":"0",
    "to_user_name":null
   },
   {...}
  ],
 "results_per_page":15,
 "since_id":0,
 "since_id_str":"0"
}

Analicemos algunas variables de la respuesta JSON que utilizaremos. Como podemos ver en la variable results_per_page, cada consulta regresa sólo 15 tweets. Para obtener los siguientes 15 tweets utilizaremos la variable next_page.

La variable results es un arreglo de objetos. Cada objeto de results contiene el usuario que creó el tweet, si está dirigido a alguien, cuándo fue creado y por supuesto el texto del tweet.

El programa en python recibe el hash tag que deseamos buscar:

python twitter_search.py "#Toluca"

El programa construye y realiza la petición de búsqueda. Después de parsear el resultado, obtenemos un mapa de llaves y valores. Por ejemplo, para acceder a la variable next_page usamos algo como search_result["next_page"]. El programa despliega todos los elementos del resultado de búsqueda, todos los elementos de un tweet y finalmente sólo los textos de los 15 tweets.

En el siguiente post extenderemos este ejemplo para obtener más de 15 tweets.

Tutorial de Grafos
Índice        Siguiente

Tutorial de Grafos

Una de las estructuras de datos que más ha llamado mi atención son los grafos. Y no sólo por la parte teórica, sino por su presencia en diversas situaciones. Uno de los ejemplos más claros son las redes sociales. Este es el primer post de una serie en la que hablaremos de grafos y algunos algoritmos.

El primer paso será construir un grafo. Resulta un tanto aburrido el estudiar grafos donde los nodos son simplemente letras y las conexiones entre ellos no tienen un significado real. Algunos libros cuando hablan de encontrar rutas usan ejemplos donde los nodos son ciudades y las conexiones son caminos entre ellas. Intentaré usar algo más atractivo para esta serie.

Después de investigar un poco las APIs de Facebook y Twitter, decidí que utilizaremos el servicio de búsqueda de Twitter, ya que no requiere autenticación, así que es muy fácil de empezar a usar. Como lenguaje de programación usaremos Python y el código estará en mercurial.

En el siguiente post comenzaremos a investigar cómo construir nuestro grafo usando la API de Twitter.

Todos los post de esta serie se irán listando a continuación:

sábado, 20 de octubre de 2012

Grafo de Lenguajes de Programación

La siguiente página muestra una red de lenguajes de programación, donde las conexiones significan que un lenguaje influenció a otro. Entre más grande sea un nodo significa que ese lenguaje ha influenciado a más lenguajes de programación.

Cuando posicionas el cursor sobre un lenguaje muestra en un color los lenguajes que lo han influenciado y en otro color los que ha influenciado. Dando clic en el nodo despliega más información acerca del lenguaje.

Esta visualización resulta muy interesante. Además, si en algún momento deseamos aprender un nuevo lenguaje, puede ser una buena guía. Por ejemplo, tal vez resulte de más utilidad aprender un lenguaje que tiene mucha influencia, porque nos puede ayudar a aprender fácilmente más lenguajes.

En la página también explican como fue generado el grafo y tiene enlaces al código.

Programming Languages Influence Network