aprendiendo ( Erlang ).

lunes, 16 de abril de 2012

Diccionario ordenado (orddict)

| 5 comentarios |

Como vimos con anterioridad un Diccionario es un tipo abstracto de datos que provee de un mapeo clave-valor. Depurando un poco la definición podemos decir que tipo orddict es una representación de un diccionario, donde las lista de elementos están ordenados por la clave del par.

El módulo orddict presenta el mismo interfaz que el 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.

Ejemplo de diccionario ordenado

Para poder ver claramente la diferencia entre dict y orddict voy a seguir el mismo ejemplo utilizado en el artículo de diccionarios. De esta forma, podremos ver los distintos comportamientos y compararlos.

1> D1 = orddict:new().
[]
2> D2 = orddict:from_list([]).
[]
3> D3 = orddict:from_list([{clave, valor}]).
[{clave, valor}]
4> orddict:store(dias_semana, lunes, D1).
[{dias_semana,lunes}]
5> orddict:store(dias_semana, [lunes, martes, miercoles, jueves, viernes, sabado, domingo], D1).
[{dias_semana,[lunes,martes,miercoles,jueves,viernes,sabado,
               domingo]}]
6> orddict:append_list(dias_semana, [lunes, martes, miercoles, jueves, viernes, sabado, domingo], D1).
[{dias_semana,[lunes,martes,miercoles,jueves,viernes,sabado,
               domingo]}]
7> orddict:append(dias_semana, lunes, D1).
[{dias_semana,[lunes]}]
8> orddict:append(fin_semana, domingo, orddict:append(fin_semana, sabado, D1)).
[{fin_semana,[sabado,domingo]}]
9> orddict:erase(dias_semana, orddict:append(dias_semana, lunes, D1)).         
[]

Los más destacable es que la representación del orddict está implementada como una lista ordenada. Y no, como vimos en el apartado de dict, con una estructura compleja y difícil de interpretar. Por decirlo de alguna manera, es más fácil visualizar la estructura y utilizarla con funciones propias.

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 = orddict:from_list([M, DS, FS]).
14> orddict:is_key(meses, Diccionario).
true
15> orddict:is_key(mes, Diccionario).  
false
16> orddict:find(meses, Diccionario).   
{ok,[enero,febrero,marzo,abril,mayo,junio,julio,agosto,
     septiembre,octubre,noviembre,diciembre]}
17> orddict:fetch_keys(Diccionario).
[dias_semana,fin_semana,meses]
18> orddict:fetch(dias_semana, Diccionario).
[lunes,martes,miercoles,jueves,viernes,sabado,domingo]
19> orddict: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]
[{dias_semana,impreso},{fin_semana,impreso},{meses,impreso}]
20> orddict:filter(fun(K,V) -> lists:member(sabado,V) end, Diccionario).      
[{dias_semana,[lunes,martes,miercoles,jueves,viernes,sabado,
               domingo]},
 {fin_semana,[sabado,domingo]}]
21> orddict:fold(fun(K,V,A) -> atom_to_list(K)++A end, "", Diccionario).         
"mesesfin_semanadias_semana"
22> orddict:merge(fun (K,V1,V2) -> {K, V1++V2} end, Diccionario, Diccionario).
[{dias_semana,{dias_semana,[lunes,martes,miercoles,jueves,
                            viernes,sabado,domingo,lunes,martes,miercoles,jueves,
                            viernes,sabado,domingo]}},
 {fin_semana,{fin_semana,[sabado,domingo,sabado,domingo]}},
 {meses,{meses,[enero,febrero,marzo,abril,mayo,junio,julio,
                agosto,septiembre,octubre,noviembre,diciembre,enero,febrero,
                marzo,abril,mayo,junio,julio,agosto,septiembre,octubre|...]}}]
23> orddict:update(meses, fun(V) -> length(V)  end, Diccionario).
[{dias_semana,[lunes,martes,miercoles,jueves,viernes,sabado,
               domingo]},
 {fin_semana,[sabado,domingo]},
 {meses,12}]
24> orddict:update(mes, fun(V) -> length(V)  end, 0, Diccionario).
[{dias_semana,[lunes,martes,miercoles,jueves,viernes,sabado,
               domingo]},
 {fin_semana,[sabado,domingo]},
 {mes,0},
 {meses,[enero,febrero,marzo,abril,mayo,junio,julio,agosto,
         septiembre,octubre,noviembre,diciembre]}]

Conclusión

El orddict nos permite tener un diccionario ordenado por la clave de forma sencilla y eficiente. El coste de inserción de los datos es algo mayor, ya que los datos se insertan de forma ordenada, pero la consulta es más eficiente al tener los datos ordenados.

Pero, ¿Cual debo utilizar? como siempre decir que depende del problema que afrontes. Lo primero que te tienes que preguntar es ¿importa el orden? si la respuesta es afirmativa en ese caso creo que lo tienes claro pero, en caso contrario la pregunta sería ¿prefiero una consulta rápida o una inserción rápida? Suponte que tienes que insertar muchos datos, y como el orden no te importa, entonces un dict te puede venir bien. Pero si el caso es, que vas a realizar muchas consultas sobre los datos entonces plantéate utilizar un orddict.

Publicar un comentario

5 comentarios:

  1. Tatis dijo...

    Hola...

    Una pregunta, estoy haciendo una tarea en Erlang sobre linux usando el gedit. Como puedo cambiarles los colores a las letras que imprimo en la terminal?

  2. Verdi dijo...

    Hola Tatis,

    #!/usr/bin/env escript
    -compile(export_all).
    main([]) ->
    io:format("\e[1;36m Hola Tatis \e[0;37m").

    En una consola Linux siempre puedes utilizar una sentencia escape para imprimir texto plano en color. Pero desgraciadamente no funciona en el EShell.

    Espero que te sea útil. Saludos.

  3. Tatis dijo...

    Hola!

    Mira ese código lo pongo en mi programa? Es que yo utilizo el -module(). -export().

    Lo probé en el io:format(" \e[1;36m texto \e[0;37m "). con eso que vos pusiste y no me funcionó...

  4. Verdi dijo...

    Hola Tatis.

    Como te comenté Erlang Shell no expande sentencias escape de este tipo, pero si la consola de Linux.

    Supongo que tu módulo Erlang será parecido a ...
    -module(color).

    -compile(export_all).

    imprimir() ->
    io:format("\e[1;36m Hola Tatis \e[0;37m").

    Entonces, una forma de lanzarlo fuera del EShell podría ser la creación de un script en Erlang.
    #!/usr/bin/env escript
    -compile(export_all).

    main([]) ->
    color:imprimir().

    Dándole permisos de ejecución puedes ver el texto en color. También puedes ejecutar tu función sin necesidad de ejecutar un script.
    $ erl -noshell -s color imprimir -s init stop
    $ erl -noshell -eval 'color:imprimir(), init:stop().'

    Espero que te sea útil. Saludos.

  5. Tatis dijo...

    Ya te entendí, muchas gracias!! Voy a probarlo en mi código :)

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