aprendiendo ( Erlang ).

jueves, 14 de julio de 2011

Diccionarios

| 0 comentarios |

Un Diccionario es un tipo abstracto de datos que provee de un mapeo clave-valor. Vamos, lo que en Java se llama Map y en otros lenguajes tablas hash o arrays asociativos.
La ventaja que proporciona esta estructura de datos es que podemos acceder a cualquier valor del diccionario en un tiempo constante. Es una diferencia notable con las listas, que necesitamos recorrerlas para obtener el valor deseado, y la velocidad de acceso dependerá de la posición en que se encuentre el dato.
La desventaja de uso, es que para que tenga un acceso constante a los datos se ralentiza la inserción de datos.
Pero, entonces, ¿cuándo es práctico usarlo?. Un caso típico, es el diccionario de constantes o semi constantes. Suponte que tu estructura se inicializa, y prácticamente no cambia a lo largo del tiempo, pero si accedes continuamente para consultarla. Es en estos casos donde se le saca rendimiento a la estructura.
Este tipo abstracto de datos se encuentra implementado en la módulo dict y sus funciones son:
  • append(Clave, Valor, Dict1) -> Dict2: añade un nuevo valor a una clave del diccionario.
  • append_list(Clave, ValList, Dict1) -> Dict2: añade nuevos valores a una clave del diccionario.
  • erase(Clave, Dict1) -> Dict2: borra una entrada del diccionario.
  • fetch(Clave, Dict) -> Valor: busca los valores de la clave en el diccionario.
  • fetch_keys(Dict) -> Claves: devuelve todas las claves del diccionario.
  • filter(Pred, Dict1) -> Dict2: selecciona todos los elementos que cumplan un predicado.
  • find(Clave, Dict) -> {ok, Valor} | error: busca por clave.
  • fold(Fun, Acc0, Dict) -> Acc1: función fold para diccionarios.
  • from_list(List) -> Dict: convierte una lista de pares en un diccionario.
  • is_key(Clave, Dict) -> bool(): test para comprobar si la clave pertenece al diccionario.
  • map(Fun, Dict1) -> Dict2: implementación de Map para diccionarios.
  • merge(Fun, Dict1, Dict2) -> Dict3: función Merge. Mezcla dos diccionarios.
  • new() -> dictionary(): crea un nuevo diccionario.
  • store(Clave, Valor, Dict1) -> Dict2: almacena un valor en el diccionario.
  • to_list(Dict) -> List: convierte un diccionario en una lista de pares.
  • update(Clave, Fun, Dict1) -> Dict2: actualiza un valor en el diccionario.
  • update(Clave, Fun, Initial, Dict1) -> Dict2: actualiza un valor en el diccionario.
  • update_counter(Clave, Increment, Dict1) -> Dict2: incrementa un valor.
A destacar, las funciones de alto nivel, que en vez de tener un parámetro como en las listas, tienen dos. Por ejemplo, la función fold en los diccionarios tiene el perfil Fun (Clave, Valor). También es destacable que la modificación de un diccionario crea un nuevo diccionario.

Creando el diccionario

Tenemos dos formas de crear un diccionario. La primera es mediante el constructor dict:new/0, y la segunda, a partir de una lista con dict:from_list/1. Veamos un ejemplo:
1> D1 = dict:new().
{dict,0,16,16,8,80,48,
      {[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[]},
      {{[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[]}}}
2> D2 = dict:from_list([]).
{dict,0,16,16,8,80,48,
      {[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[]},
      {{[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[]}}}
3> D3 = dict:from_list([{clave, valor}]).
{dict,1,16,16,8,80,48,
      {[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[]},
      {{[],[],[],[],[],
        [[clave|valor]],
        [],[],[],[],[],[],[],[],[],[]}}}
En el comando 1, hemos creado un diccionario con el constructor. Lo destacable es el resultado de la llamada que nos proporciona la estructura interna del diccionario. Estructura que no vamos a utilizar por que para ello, ya se encarga la librería.
En los comandos 2 y 3, hemos creado el diccionario con la función dict:from_list/1; en el primero, obtenemos la misma estructura que con el constructor por defecto; y en el segundo, introducimos un par de clave-valor.

Añadiendo elementos

Ya hemos visto como una forma de añadir elementos a la lista con dict:from_list/1. Ahora veremos otros:
4> dict:store(dias_semana, lunes, D1).                                                              
{dict,1,16,16,8,80,48,
      {[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[]},
      {{[],
        [[dias_semana|lunes]],
        [],[],[],[],[],[],[],[],[],[],[],[],[],[]}}}
5> dict:store(dias_semana, [lunes, martes, miercoles, jueves, viernes, sabado, domingo], D1).
{dict,1,16,16,8,80,48,
      {[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[]},
      {{[],
        [[dias_semana,lunes,martes,miercoles,jueves,viernes,sabado,
          domingo]],
        [],[],[],[],[],[],[],[],[],[],[],[],[],[]}}}
Mediante la función dict:store/3 añadimos elementos al diccionario de forma sencilla, obteniéndose una nueva estructura con los datos. Análogamente, podemos utilizar también la función dict:append/3 y dict:append_list/3:
6> dict:append_list(dias_semana, [lunes, martes, miercoles, jueves, viernes, sabado, domingo], D1).
{dict,1,16,16,8,80,48,
      {[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[]},
      {{[],
        [[dias_semana,lunes,martes,miercoles,jueves,viernes,sabado,
          domingo]], 
        [],[],[],[],[],[],[],[],[],[],[],[],[],[]}}}
7> dict:append(dias_semana, lunes, D1).
{dict,1,16,16,8,80,48, 
      {[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[]},
      {{[],
        [[dias_semana,lunes]],
        [],[],[],[],[],[],[],[],[],[],[],[],[],[]}}}
8> dict:append(fin_semana, domingo, dict:append(fin_semana, sabado, D1)).
{dict,1,16,16,8,80,48,
      {[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[]},
      {{[],
        [[fin_semana,sabado,domingo]],
        [],[],[],[],[],[],[],[],[],[],[],[],[],[]}}}
La única diferencia entre dict:append/3 y dict:store/3 radica en que la función store sobreescribe el valor si existe la clave en el diccionario y append añade el valor a los existentes.

Borrando elementos

Para el borrado tenemos la función dict:erase/2. La verdad es que tiene poco que explicar.
9> dict:erase(dias_semana, dict:append(dias_semana, lunes, D1)).         
{dict,0,16,16,8,80,48,
      {[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[]},
      {{[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[]}}}

Consultando el diccionario

Para consultar el diccionario vamos a crear un nuevo diccionario con algunos datos más:
10> DS = {dias_semana, [lunes, martes, miercoles, jueves, viernes, sabado, domingo]}.       
{dias_semana,[lunes,martes,miercoles,jueves,viernes,sabado,
              domingo]}
11> M = {meses, [enero, febrero, marzo, abril, mayo, junio, julio, agosto, septiembre, octubre, noviembre, diciembre]}.
{meses,[enero,febrero,marzo,abril,mayo,junio,julio,agosto,
        septiembre,octubre,noviembre,diciembre]}
12> FS = {fin_semana, [sabado, domingo]}.
{fin_semana,[sabado,domingo]}
13> Diccionario = dict:from_list([M, DS, FS]).
{dict,3,16,16,8,80,48,
      {[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[]},
      {{[],
        [[dias_semana,lunes,martes,miercoles,jueves,viernes,sabado,
          domingo],
         [fin_semana,sabado,domingo]],
        [],
        [[meses,enero,febrero,marzo,abril,mayo,junio,julio,agosto,
          septiembre,octubre,noviembre,diciembre]],
        [],[],[],[],[],[],[],[],[],[],[],[]}}}
Las funciones para estos menesteres son: dict:is_key/2, dict:find/2, dict:fetch_keys/1 y dict:fetch/2. Todas ellas nos permite consultar los datos del diccionario. Y Como es de rigor, y como el movimiento se demuestra andando, aquí van los ejemplos de consulta sobre nuestro diccionario.
14> dict:is_key(meses, Diccionario).
true
15> dict:is_key(mes, Diccionario).  
false
16> dict:find(meses, Diccionario).   
{ok,[enero,febrero,marzo,abril,mayo,junio,julio,agosto,
     septiembre,octubre,noviembre,diciembre]}
17> dict:fetch_keys(Diccionario).         
[fin_semana,dias_semana,meses]
18> dict:fetch(dias_semana, Diccionario).
[lunes,martes,miercoles,jueves,viernes,sabado,domingo]

Funciones de orden superior (o de alto nivel)

Como ya se indico las Fun's tienen un formato distinto. Veamos ejemplos. Hemos utilizado la función dict:map/2 para imprimir los pares clave-valor.
19> dict:map( fun(K,V) -> io:format("~p -> ~p~n", [K,V]), impreso end, Diccionario).
dias_semana -> [lunes,martes,miercoles,jueves,viernes,sabado,domingo]
fin_semana -> [sabado,domingo]
meses -> [enero,febrero,marzo,abril,mayo,junio,julio,agosto,septiembre,
          octubre,noviembre,diciembre]
{dict,3,16,16,8,80,48,
      {[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[]},
      {{[],
        [[dias_semana|impreso],[fin_semana|impreso]],
        [],
        [[meses|impreso]],
        [],[],[],[],[],[],[],[],[],[],[],[]}}}
La función dict:filter/2 para obtener un diccionario con los pares cuyo valores tengan el valor sabado.
20> dict:filter(fun(K,V) -> lists:member(sabado,V) end, Diccionario).      
{dict,2,16,16,8,80,48,
      {[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[]},
      {{[],
        [[dias_semana,lunes,martes,miercoles,jueves,viernes,sabado,
          domingo],
         [fin_semana,sabado,domingo]],
        [],[],[],[],[],[],[],[],[],[],[],[],[],[]}}}
Con la función dict:fold/3 hemos obtenido una cadena con las claves.
21> dict:fold(fun(K,V,A) -> atom_to_list(K)++A end, "", Diccionario).         
"fin_semanadias_semanameses"
Con dict:merge/3 he mezclado dos diccionarios de la siguiente forma:
22> dict:merge(fun (K,V1,V2) -> {K, V1++V2} end, Diccionario, Diccionario).                                  
{dict,3,16,16,8,80,48,
      {[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[]},
      {{[],
        [[dias_semana|
          {dias_semana,[lunes,martes,miercoles,jueves,viernes,sabado,
                        domingo,lunes,martes,miercoles,jueves,viernes|...]}],
         [fin_semana|{fin_semana,[sabado,domingo,sabado,domingo]}]],
        [],
        [[meses|
          {meses,[enero,febrero,marzo,abril,mayo,junio,julio,agosto,
                  septiembre,octubre|...]}]],
        [],[],[],[],[],[],[],[],[],[],[],[]}}}
Con la función dict:update/3/4 vamos a actualizar la entrada de meses por la longitud de la lista de meses.
23> dict:update(meses, fun(V) -> length(V)  end, Diccionario).
{dict,3,16,16,8,80,48,
      {[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[]},
      {{[],
        [[dias_semana,lunes,martes,miercoles,jueves,viernes,sabado,
          domingo],
         [fin_semana,sabado,domingo]],
        [],
        [[meses|12]],
        [],[],[],[],[],[],[],[],[],[],[],[]}}}
24> dict:update(mes, fun(V) -> length(V)  end, 0, Diccionario).
{dict,4,16,16,8,80,48,
      {[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[]},
      {{[],
        [[dias_semana,lunes,martes,miercoles,jueves,viernes,sabado,
          domingo],
         [fin_semana,sabado,domingo]],
        [],
        [[meses,enero,febrero,marzo,abril,mayo,junio,julio,agosto,
          septiembre,octubre,noviembre,diciembre],
         [mes|0]],
        [],[],[],[],[],[],[],[],[],[],[],[]}}}

Y con esto y un bizcocho ...

Hay otra estructura de datos que tiene una naturaleza similar. Tablas ETS, que están diseñadas para grandes cantidades de datos y el uso intensivo, que por supuesto, veremos en otro post.

Publicar un comentario en la entrada

0 comentarios:

 
Licencia Creative Commons
Aprendiendo Erlang por Verdi se encuentra bajo una Licencia Creative Commons Atribución-NoComercial-CompartirIgual 3.0 Unported.