Re: [Grulic-dev] estructura de datos para mantener ordenado

> El día 15 de febrero de 2010 11:42, Domingo Becker
> <domingobecker@???> escribió:

> La implementación con template dada en [1], que es
> sospechosamente corta, menos de 130 líneas, parece ser muy
> buena. La verdad es que anda muy mal. No me puse a ver
> internamente dónde le erraron.

¿Verificaste en esta implementación que maxlevel esté en un valor adecuado
no?
Igual los templates generan un overhead importante. ¿Qué tasa de indexación
obtuviste con esta versión? Sería interesante compartas tus métricas.

> ...
> La implementación en C++ que si funcionó es la de [2], que no
> usa templates y usa un typedef poco feliz. Para cambiar las
> estructuras de datos de la clave y el dato, hay ciertos
> prerequisitos que se deben cumplir. Surgen de la lectura del
> código fuente. Pero no he tenido problemas para hacerlo, en
> realidad fue muy rápido. Estoy usando un nivel de 25, y los
> resultados obtenidos son los siguientes, para mi caso particular:
>
> Indexando con SkipList sin templates
> L:100000 A:324182
> Hasta aqui 00:00:23.38.
> L:200000 A:637767
> Hasta aqui 00:00:47.02.
> L:300000 A:947398
> Hasta aqui 00:01:10.72.
> L:400000 A:1250356
> Hasta aqui 00:01:34.25.
> L:500000 A:1549080
> Hasta aqui 00:01:57.72.
> L:559234 A:1723965
> Listo.
> Tomo 00:02:11.61 para armar el SkipList.
>
> Indexando con std::map
> L:100000 A:324182
> Hasta aqui 00:00:25.05.
> L:200000 A:637767
> Hasta aqui 00:00:50.14.
> L:300000 A:947398
> Hasta aqui 00:01:15.39.
> L:400000 A:1250356
> Hasta aqui 00:01:40.64.
> L:500000 A:1549080
> Hasta aqui 00:02:05.84.
> L:559234 A:1723965
> Listo.
> Tomo 00:02:20.75 para armar el mapa.
>
> La indexación genera 1723965 registros y con Skip Lists se
> demora 11 segundos menos, 8% menos, que la que usa std::map.
> En ambos, el crecimiento es prácticamente lineal.

Nada mal. A razón de 13.000 reg/segundo c/ skiplists y 12.000 con map.
La verdad que esperaba una diferencia mayor. Bien por maps!

>
> Bien, mi elección es entonces Skip Lists. Ahora voy a
> proceder a modificar el código fuente para hacerla genérica e
> implementarla en disco, con caché en memoria. No parece ser
> mucho trabajo dado que son 360 líneas de código, o sea, nada,
> para los trabajos promedio que normalmente hago. Igualmente
> va a tomar un tiempo, pero ya tengo lo que buscaba.

Te recomiendo enfáticamente echarle un vistazo a la librería BerkeleyDB
antes de encarar ese desarrollo. Si bien, como decís no es mucho esfuerzo,
lo que buscás ya está resuelto en BerkeleyDB, es muy rápido y robusto y muy
utilizado en todo el mundo.

> Para los que no se dieron cuenta, la implementación
> resultante compite de igual a igual con un gestor de bases de
> datos comercial. La diferencia es que, como lo ha hecho uno,
> si hay problemas lo puede resolver uno sin necesidad de
> hablar a nadie (no hay dependencias en un punto clave que es
> la gestión de tablas de datos). Calculo que por eso no hay
> serializaciones buenas hechas con licencias GPL o parecidas,
> por el valor comercial que tienen.

A igual hardware ningún gestor ACID le va a ganar en performance a esto pero
desde la perspectiva de usabilidad y fiabilidad, el gestor se lleva las
palmas.

Saludos,
Fernando.