Tipos de Datos en Erlang (II): Diccionarios

Siguiendo con la edición de tipos de datos en Erlang vamos a repasar en esta entrega los diccionarios. Los diccionarios son conocidos genéricamente como hash. A diferencia de los arrays vistos en la entrega anterior en este caso se permite emplear un texto, número o átomo en lugar de restringirse a un índice numérico.

Los datos que se almacenan en un diccionario son conocidos como pares clave-valor. En Erlang disponemos de dos módulos que nos proporcionan diccionarios: dict es un diccionario genérico y orddict que implementa además un sistema de ordenación por clave.

Ambos módulos tienen las mismas funciones, por lo que podríamos emplear uno u otro de forma independiente. Según lo que queramos conseguir. Con el módulo estándar conseguimos mayor velocidad a la hora de insertar y eliminar elementos, mientras que con el diccionario ordenado podemos conseguir una mayor velocidad de lectura.

Iniciando un Diccionario

Los diccionarios se crean con el método new/0. Este método retorna una estructura de diccionario vacía. Podemos usarlo de cualquiera de las siguientes formas:

%% diccionario normal
Dict = dict:new().

%% diccionario ordenado
DictOrd = orddict:new().

Manejando datos

Se puede almacenar un valor con el uso de la función store/3. Si el valor existe se intercambia por el nuevo valor proporcionado. Para obtener cualquier clave del diccionario empleamos fetch/2 y para eliminar una entrada del diccionario erase/2. Un ejemplo de uso:

%% creamos el diccionario
Dict0 = dict:new().

%% almacena elementos
Dict1 = dict:store(a, "alpha", Dict0).

%% obtiene el elemento
dict:fetch(a, Dict1).

%% elimina el valor
Dict2 = dict:erase(a, Dict1).

Es importante reseñar que el fetch/2 espera encontrar la clave y retornar el Valor por lo que, si no encuentra la clave lanza una excepción. Podemos emplear también find/2 que retorna error en caso de no encontrar el valor o {ok, Value} en caso de encontrarlo.

A medida que vayamos insertando valores podemos saber el tamaño del diccionario (la cantidad de claves que contiene) con la función size/1.

Además de estas operaciones básicas, podemos emplear otras funciones que nos ayudan a agregar datos a una clave como son el caso de las funciones append/2 y append_list/3. Estas funciones insertan una clave con un valor en caso de no existir la clave o un conjunto de valores en el segundo caso. En caso de existir la clave, el valor o valores se agregan a la clave. Un ejemplo:

%% Valor inicial
Dict1 = dict:store(a, "25", dict:new()).

%% agregar elemento:
dict:append(a, "30", Dict1).
% a = ["25", "30"].

%% agregar elementos:
dict:append(a, ["30", "50"], Dict1).
% a = ["25", "30", "50"].

Otra forma de manipulación de datos que propone el módulo es a través de las funciones update/3 y update/4. Estas funciones permiten pasar una clausura a la que se le pasa el valor de la clave y puede retornar la modificación a realizar. Esto facilita la tarea de realizar modificaciones dentro de un diccionario. Un ejemplo:

%% valor inicial
Dict0 = dict:store(a, 25, dict:new()).

%% multiplicamos por 2
Dict1 = dict:update(a, fun(Old) ->
    Old * 2
end, Dict0).
% a = 50

%% multiplicamos por 2
Dict2 = dict:update(b, fun(Old) ->
    Old * 2
end, 1, Dict0).
% a = 25, b = 1

En el primer caso la clave existe y se aplica la función sobre el valor encontrado. En el segundo caso el valor de la clave no se encuentra y se aplica el valor inicial. En caso de que la clave no exista y no se especifique un valor inicial se lanza una excepción.

Recorriendo el diccionario

Para recorrer el diccionario podemos emplear las funciones filter/2, fold/3 y map/2. Con la primera función podemos hacer una criba y extraer en una lista solo los elementos que necesitemos. Con fold/3 se pueden extraer datos acumulados o contadores. La última función map/2 obtiene datos procesados de cada elementos dentro de un diccionario. Por ejemplo:

%% valor inicial
Dict0 = dict:new().
Dict1 = dict:append(a, 2, Dict0).
Dict2 = dict:append(b, 5, Dict1).
Dict3 = dict:append(c, 10, Dict2).
DictN = dict:append(z, 50, Dict3).

%% filtrado de pares
dict:filter(fun(Key, Value) ->
    Value rem 2 =:= 0
end, DictN).

%% sumatorio
dict:fold(fun(Key, Value, Sum) ->
    Sum + Value
end, , DictN).

%% multiplicación por 2
dict:map(fun(Key, Value) ->
    Value * 2
end, DictN).

Con datos más complejos como estructuras permite filtrar por otro tipo de datos y la clausura puede ser más compleja para realizar filtrados más complejos, procesados más completos o acumulados más precisos.

Por último, se puede emplear la función merge/3. Esta función mezcla dos diccionarios en uno solo. El primer parámetro corresponde a una clausura que se emplea en caso de colisión de claves. El resto de elementos se mezclan sin intervención de la clausura:

%% valor inicial
Dict0 = dict:new().
Dict1 = dict:store(a, 2, Dict0).
Dict2 = dict:store(b, 5, Dict1).
Dict3 = dict:store(a, 3, Dict2).

%% mezcla
dict:merge(fun(Clave, Val1, Val2) ->
    [Val1, Val2]
end, Dict2, Dict3).
% a = [2,3]; b = 5

Conversiones

Una de las facilidades que nos proporcionan los diccionarios es la posibilidad de transformarse desde y hacia listas. Las funciones que empleamos para esto son from_list/1 y to_list/1 respectivamente. La conversión se realiza en forma de lista de propiedades por lo que una vez convertida podemos seguir trabajando con la lista de propiedades y el módulo proplists.

Igualmente podemos tratar una lista de propiedades convertida como un diccionario ordenado o un diccionario estándar:

%% lista de propiedades
ListProp = [{a, 25}, {b, 5}].

%% A diccionario:
Dict = dict:from_list(ListProp).

%% A lista de propiedades:
ListProp1 = dict:to_list(Dict).

Banco de pruebas

Realizando un banco de pruebas entre las listas de propiedades, diccionarios y diccionarios ordenados, obtenemos los siguientes resultados. En una muestra de un millón de elementos siendo su generador:

LP = [ {X,X*2} || X <- lists:seq(1,10000) ].
OD = orddict:from_list(LP).
UD = dict:from_list(LP).

Apoyándome en estas clausuras para medir los datos de resultado y ejecutando varias pruebas obtenemos:

%% now
Now = fun() ->
    {Mega,Sec,Mili} = now(),
    (Mega * 1000000) + Sec + (Mili / 1000000)
end.

%% medición
Mide = fun(ToDo) ->
    Ini = Now(),
    ToDo(),
    Now() - Ini
end.

%% conversión desde listas (escritura, resultado en segundos)
Mide(fun() -> orddict:from_list(LP) end).
% 2.1700518131256104
Mide(fun() -> dictffrom_list(LP) end).
% 0.018949031829833984

%% conversion a lista (lectura, en segundos)
Mide(fun() -> orddict:to_list(OD) end).
% 0.0000221729278564453
Mide(fun() -> dicttto_list(UD) end).
% 0.0014319419860839844

Como habíamos visto antes, la lista ordenada es más lenta en la escritura y mucho más rápida en la lectura. Ahora probaremos los accesos de lectura. Para ello vamos a generar un acceso de índices aleatorios:

%% accesos
random:seed().
Accesos = [ random:uniform(10000) || X <- lists:seq(1, 10000) ].

Mide(fun() -> [ orddict:fetch(X, OD) || X <- Accesos ] end).
% 1.172424077987671
Mide(fun() -> [ dict:fetch(X, UD) || X <- Accesos ] end).
% 0.056600093841552734

Mide(fun() -> [ orddict:find(X, OD) || X <- Accesos ] end).
% 1.6827430725097656
Mide(fun() -> [ dict:find(X, UD) || X <- Accesos ] end).
% 0.05847620964050293

Mide(fun() -> [ proplists:get_value(X, LP) || X <- Accesos ] end).
% 2.782465934753418
Mide(fun() -> [ lists:keyfind(X, 1, LP) || X <- Accesos ] end).
% 0.3408520221710205

En este caso, el peor método resultan ser las listas de propiedades, seguidos de los diccionarios ordenados, la búsqueda por lista y el mejor el diccionario simple. Lo cual resulta en una sorpresa ya que la ordenación del diccionario ordenado le facilita un acceso más rápido por lo que es curioso que el diccionario simple sea más rápido en esta prueba.

La última prueba, de escritura:

%% escrituras
random:seed().
Escrituras = [ random:uniform(10000) || X <- lists:seq(1, 10000) ].

Mide(fun() -> lists:foldl(fun(X,Acc) -> orddict:store(X, X*2, Acc) end, orddict:new(), Escrituras) end).
% 0.8920290470123291
Mide(fun() -> lists:foldl(fun(X,Acc) -> dict:store(X, X*2, Acc) end, dict:new(), Escrituras) end).
% 0.09263777732849121
Mide(fun() -> lists:foldl(fun(X,Acc) -> [{X, X*2}] end, [], Escrituras) end).
% 0.05460095405578613

En este último caso se ve más rápido de nuevo el diccionario simple frente al diccionario ordenado y aún más rápida la inserción de listas. En este caso es lógico ya que el manejo a este nivel de lista de propiedades es manejar únicamente una lista con tuplas de dos elementos.

Conclusiones

Tras revisar estos módulos me queda una muy buena sensación al ver que dict es un módulo que facilita y acelera las operaciones básicas en base a la estructura de datos acelerando en ciertos aspectos el uso típico que se suele realizar con las listas de propiedades y además ofreciendo un enlace y compatibilidad adecuadas para que puedan convivir y beneficiarse de los mejores aspectos de cada método.