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

Página superior
Adjuntos:
+ (text/plain)
Eliminar este mensaje
Responder a este mensaje
Autor: Edgardo Hames
Fecha:  
A: Lista de desarrollo de software libre
Asunto: Re: [Grulic-dev] estructura de datos para mantener ordenado
2010/1/31 Domingo Becker <>:
> El día 30 de enero de 2010 11:22, Edgardo Hames <> escribió:
>> Encontré esta discusión en Stack Overflow:
>>
>> http://stackoverflow.com/questions/1822114/c-map-insertion-and-lookup-performance-and-storage-overhead
>>
>
> Excelente discusión.
> El que preguntaba tiene el mismo problema, solo que los datos de él
> son 130 millones de registros.
> Me abrió un poco la mente respecto a los algoritmos a utilizar.


;-)

>> Metete con la STL de C++: tiene muchísimos containers, cada uno de
>> ellos optimizado para ciertas operaciones. Por lo que entiendo de tu
>> mail, a vos te interesan la inserción y la búsqueda eficientes.
>
> Sí, inserción y búsqueda eficiente, es más, serialización, o más aun,
> que la implementación del algoritmo sea trabajando sobre el disco y
> haciendo cache en memoria de lo que haga falta para optimizar.


Uf! Ahí me mataste, peeero, creo que vos podés hacer un cacho de
trampa creando un ramdisk o usando un archivo mapeado en memoria para
acelerar el acceso (ver: mmap(2)).

Edición posterior: si serializás la estructura de datos cargada, no
volvés a insertar los elementos, entendí? En caso afirmativo, fijate
en:
http://stackoverflow.com/questions/137659/persistence-of-stdmap-in-c

>> Si contás un poquito más sobre el tipo de datos que vas a guardar,
>> quizás podamos encontrar algo más puntual.
>
> En un sistema que tengo, debo integrar consultas a un padrón de 550
> mil registros de nombres y apellidos. Debo buscar por nombre, y se me
> había ocurrido armar un índice de nombres tal que un registro con
> "nombre1 nombre2 apellido" generaría 3 entradas en el índice. De esa
> forma optimizar la forma de la búsqueda y hacerlo con más libertad.
> Por ejemplo, para el registro mencionado "nombre2 nombre1" me
> encontrarían el registro si lo separo por palabras y luego consulto si
> esas palabras están. Y creo que funcionaría muy rápido.


Con esta descripción y asumiendo que tenés la estructura serializada,
lo más importante es una búsqueda eficiente. La búsqueda en un mapa de
la STL parece ser O(log n) lo cual tiene sentido si está implementada
con un árbol. Si eso no te alcanza, también podés probar con un
std::hash_map (pero es del estándar nuevo así que no todos los
compiladores la implementan):

http://www.sgi.com/tech/stl/hash_map.html

> Si traigo la tabla a memoria, ocuparía aproximadamente 90 megas con
> todos los datos que necesito. También hace dudar si es viable, por la
> cantidad de memoria que usaría.


Hay muchos strings que se repiten: por ejemplo, el string Domingo es
el mismo en Domingo Becker, Domingo Faustino Sarmiento. Por lo tanto,
es posible que el patrón flyweight sirva:

http://en.wikipedia.org/wiki/Flyweight_pattern

Ya está implementado en boost y debería reducir bastante el uso de memoria:

http://www.boost.org/doc/libs/1_41_0/libs/flyweight/doc/index.html

En la documentación, hay un ejemplo que ataca un problema de usuarios y nombres!

http://www.boost.org/doc/libs/1_41_0/libs/flyweight/doc/tutorial/basics.html

Éxitos,
Edgardo

--
The mere formulation of a problem is far more essential than its solution,
which may be merely a matter of mathematical or experimental skills.
-- Albert Einstein