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

Página superior
Adjuntos:
+ (text/plain)
Eliminar este mensaje
Responder a este mensaje
Autor: Domingo Becker
Fecha:  
A: Fernando Hevia, Lista de desarrollo de software libre
Asunto: Re: [Grulic-dev] estructura de datos para mantener ordenado
El día 15 de febrero de 2010 11:42, Domingo Becker
<> escribió:
> El día 15 de febrero de 2010 11:17, Fernando Hevia
> <> escribió:
>> Recién llego a la oficina y veo tu mail. A simple vista el problema debería
>> estar aquí:
>>
>>   #define SKIPLIST_MAXLEVEL 6 // maximum node level
>>
>
> Le puse 24 y actualmente va muy rápido.
> Pero estoy con (int, int) para (clave, dato). Tengo que probar con los
> tipos de datos que me interesan y no he terminado.
> Ahora veo si termino con esa prueba.
>
> Intenté con una implementación con template y va muy lento, empecé a
> dudar si estaba bien hecha.


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.

Hay otras implementaciones con templates, pero las descarté porque
usan excepciones. Detesto las excepciones. No sé como pudieron
inventar semejante disparate.


> Vuelvo con la que si funcionó y le estoy cambiando los typedef.
>


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.

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.

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.

[1] http://www.mathcs.duq.edu/drozdek/DSinCpp/genSkipL.h

[2] http://www.superliminal.com/sources/sources.htm

Saludos y gracias a todos los que contestaron mis mensajes.

Domingo Becker