julio 31, 2008

¿Sabes lo que es un hashmap?

Para los programadores de Java este concepto tal vez no sea tan extraño pues el uso de hashmaps es común, pero para los programadores de Delphi puede sonarles a nuevo.
Un hashmap es una estructura de datos que permite crear un mapa en memoria para la rápida identificación de elementos a partir de un dato usado como llave. Puedes decir: ok si conozco muchas estructuras de datos que permiten hacer eso, ¿cual es la diferencia con los hashmaps?; bien, la principal es que los hashmaps son verdaderamente rápidos.
La librería JCL incluye varias clases para la implementación de diferentes tipos de hashmaps, aquí mostraré una de estas para poder encontrar una cadena a partir de el valor de otra:

Y una vez hecho esto, encontrar una aguja dentro de ese gran pajar se reduce a una simple instrucción:
ShowMessage (Map.GetValue ('Llave5670'));
En este caso hemos ejemplificado usando cadenas (que incluso usando hashmaps se gana mucha velocidad respecto a utilizar los clásicos derivados de TStrings, TStringList), pero las posibilidades se multiplican si te das cuenta de que puedes mapear grandes cantidades de objetos usando esta técnica. Estos pequeños grandes tips hacen la diferencia entre lo que puede parecer un lento cacharro, o un veloz jet a la hora de trabajar con cantidades de datos muy considerables.

12 comentarios:

  1. Y.... ¿Cómo se utilizaría con objetos? ¿Se podría busca un objeto por el valor de cualquiera de sus propiedades, o sería por una "clave principal"?

    ResponderEliminar
  2. Me pregunto si sera mucho mas rápido que usar un TStringList ordenado (Sorted:= TRUE), en ese caso el método IndexOf utiliza una búsqueda de tipo binaria que me parece bastante rápido. Además con el TStringList también puedes manejar objetos (en realidad cualquier puntero) con el método AddObject.

    Tendríamos que comparar, pero no creo que pueda ser muchos mas rápido.

    ResponderEliminar
  3. Que tal Domingo!...

    Pues te tengo noticias, no solo el hashmap es más rápido, sino que es Violentamente más rápido!!

    Entre la JCL hay un demo que permite comparar el desempeño de las diferentes clases para manejo de datos estructurados llamado "Container Performance", ahi puedes probar que clase te sirve mejor para que caso.

    Como lo puedes probar es con un ejemplo sencillo y simple:

    Aqui lo que hago es agregar a ambas clases 100,000 cadenas aleatorias y medir el tiempo que se tardó la clase en indexarlas; despues hago 100,000 lecturas preguntando también por diferentes cadenas y midiendo el tiempo que se tardó en resolver todas mis peticiones, y los resultados son los siguientes en mi equipo:

    TStringList Sorted:
    Agregar Todas : 921.0 ms
    100 mil lecturas : 942.0 ms

    TestJclStrStrHashMap:
    Agregar Todas: 50.0 ms
    100 mil lecturas: 90.0 ms

    Asi que tengo una mejora en velocidad del 90% mas o menos (que mas da unas decimas arriba o abajo)

    Incluso en la VCL hay una clase THashedStringList que sería el equivalente de usar estas listas de cadenas pero con el beneficio de la estructura de los Hashes, pero aún esta clase no resulta tan rápida como la implementación de los Hashes del la JCL.

    Aquí esta el código que use para probar mis números, solo se necesita un Tstringgrid y un botón en un formulario para que funcione.


    uses JclContainerIntf, JclHashMaps;

    const
    ResultFormat = '%.1f ms';
    MsecsPerDay = 24 * 60 * 60 * 1000;

    function GenId(Value: Integer): string;
    begin
    Result := IntToStr(random(Value));
    end;

    procedure TestJclStrStrHashMap(Results: TStrings);
    var
    Map: IJclStrStrMap;
    I: Integer;
    Res: string;
    Start: TDateTime;
    begin
    Randomize;
    Screen.Cursor := crHourGlass;
    try
    Start := Now;
    Map := TJclStrStrHashMap.Create(100000);
    for I := 0 to 100000 do
    Map.PutValue(GenId(123), '');
    Results[1] := Format(ResultFormat, [(Now - Start) * MsecsPerDay]);
    Start := Now;
    for I := 0 to 100000 do
    Res := Map.GetValue(GenId(123));
    Results[2] := Format(ResultFormat, [(Now - Start) * MsecsPerDay]);
    Start := Now;
    Map.Clear;
    Results[3] := Format(ResultFormat, [(Now - Start) * MsecsPerDay]);
    finally
    Screen.Cursor := crDefault;
    end;
    end;

    procedure TestStringList(Results: TStrings);
    var
    Map: TStringList;
    I: Integer;
    Index: Integer;
    Start: TDateTime;
    begin
    Randomize;
    Screen.Cursor := crHourGlass;
    try
    Start := Now;
    Map := TStringList.Create;
    Map.Sorted := True;
    for I := 0 to 100000 do
    Map.Add( GenId(123));
    Results[1] := Format(ResultFormat, [(Now - Start) * MsecsPerDay]);
    Start := Now;
    for I := 0 to 100000 do
    Index := Map.IndexOf(GenId(123));
    Results[2] := Format(ResultFormat, [(Now - Start) * MsecsPerDay]);
    Start := Now;
    Map.Clear;
    Results[3] := Format(ResultFormat, [(Now - Start) * MsecsPerDay]);
    finally
    Screen.Cursor := crDefault;
    end;
    end;

    procedure TForm2.Button1Click(Sender: TObject);
    begin
    TestStringList(JvStringGrid1.Cols[1]);
    TestJclStrStrHashMap(JvStringGrid1.Cols[2]);
    end;

    En este artículo he sido muy austero, en el próximo ahondaré mas en este tema de los hashes y los tips que utilizo para sacarles el mejor provecho.

    Saludos =:-)

    ResponderEliminar
  4. Jeje ... ya dije que había que comparar. Y ahora, con datos en la mano, ya no tengo mas que decir.

    Tendré que echarle un vistazo a esas clases por dentro para ver que las hace tan rápidas

    Saludos

    ResponderEliminar
  5. Efectivamente, poco queda por decir... solo que deberemos utilizar los hashmap a partir de ahora...

    ResponderEliminar
  6. Anónimo6:03 p.m.

    Al parecer la diferencia radica en que para el caso del hashmap ya se tienen definidas el total de cadenas que seran almacenadas, mientras que para el TStringList no; estoy conlleva a que cada vez que se agregue una cadena al stringlist se verifique la disponibilidad de la memoria y se redimensione la capacidad del objeto.

    ResponderEliminar
  7. Anónimo8:39 a.m.

    bueno se les agradece por lo naqui consignado me ha servido de mucho ok osea...

    ResponderEliminar
  8. Hola Carlos.

    Primero que nada la diferencia entre 942 ms y 90 ms no es 90% sino 1000% (10 veces más) :p.

    Por otro lado, como comentaron más arriba, el tiempo de agregado depende en buena medida de la cantidad de memoria reservada desde el inicio (habría que hacer otra prueba con la propiedad Capacity inicializada a 100000).

    En cuanto a la búsqueda, no dudo que sea más rápida la clase especializada. Sería interesante ver cómo guarda las cadenas de caracteres y la manera en que realiza la indexación.

    Gracias por darnos a conocer esta clase TJclStrStrHashMap.

    Al González. :)

    ResponderEliminar
  9. hi guys ... I was very pleased to read the information in this article ... was of great interest and would love to get a lot more information about¿Sabes lo que es un hashmap?

    ResponderEliminar
  10. Anónimo12:56 p.m.

    eso no es un hashmap, es un map

    ResponderEliminar
  11. Me gustaria a mi tomar un curso en programacion web, si alguien sabe de alguno por favor digame donde puedo inscribirme que voy corriendo en el gol

    ResponderEliminar
  12. Anónimo9:41 a.m.

    I want you (She's so heavy)

    ResponderEliminar