¿Recomendación para lista de búsqueda?

"Benton" wrote in message
news:uAaVn$

Necesito tener una lista en memoria con aproximadamente cinco mil valores
string. En esta lista debo poder buscar por "inicios" de longitud
variable. Por ejemplo,
una consulta debe regresar todos los valores que comienzen con "M", o
todos los que comienzen con "MK", o con "MK1" y así sucesivamente.

Agradezco ideas o recomendaciones de técnicas para implementar esto de una
forma óptima. Uso el framework 2.0

Mete los valores en un array de strings y ordénalo por orden alfabético.
Utiliza una búsqueda dicotómica para localizar el primer valor que comience
por el prefijo que deseas. Seguidamente recorre los elementos por orden de
índice hasta llegar al primer elemento que no tenga el prefijo buscado.

Si lo que buscas es rendimiento para inserción de elementos y búsquedas,
entiendo que una tabla hash sería la solución que te proporcionase mayor
rendimiento.
La complejidad de una búsqueda dicotómica en la lista, si no recuerdo mal,
sería algo así como:

O(nk log n) = O(n0 log n) = O(log n)

Sin embargo en una tabla hash, tenemos complejidades que van de O(1) en el
mejor de los casos a O(n) en el peor. Dado que son 'sólamente' unos 5000
registros, creo que no habría muchas redispersiones en el hash, de forma que
lo considero una solución apropiada.

Espero que te sirva de ayuda.

Saludos

Fran Peula Ariza

"Alberto Poblacion" escribió:

"Benton" wrote in message
news:uAaVn$
> Necesito tener una lista en memoria con aproximadamente cinco mil valores
> string. En esta lista debo poder buscar por "inicios" de longitud
> variable. Por ejemplo,
> una consulta debe regresar todos los valores que comienzen con "M", o
> todos los que comienzen con "MK", o con "MK1" y así sucesivamente.
>
> Agradezco ideas o recomendaciones de técnicas para implementar esto de una
> forma óptima. Uso el framework 2.0

Mete los valores en un array de strings y ordénalo por orden alfabético.
Utiliza una búsqueda dicotómica para localizar el primer valor que comience
por el prefijo que deseas. Seguidamente recorre los elementos por orden de
índice hasta llegar al primer elemento que no tenga el prefijo buscado.

"Fran Peula Ariza" wrote in
message news:

Si lo que buscas es rendimiento para inserción de elementos y búsquedas,
entiendo que una tabla hash sería la solución que te proporcionase mayor
rendimiento.
La complejidad de una búsqueda dicotómica en la lista, si no recuerdo mal,
sería algo así como:

O(nk log n) = O(n0 log n) = O(log n)

Sin embargo en una tabla hash, tenemos complejidades que van de O(1) en el
mejor de los casos a O(n) en el peor. Dado que son 'sólamente' unos 5000
registros, creo que no habría muchas redispersiones en el hash, de forma
que
lo considero una solución apropiada.

La tabla de Hash no permite buscar todos los elementos que empiecen por
un prefijo determinado, tal como se planteaba en la consulta original. Para
resolver esa consulta es necesario recorrer uno por uno todos los elementos
de la tabla de hash, con lo que tendremos una búsqueda de O(n) en el 100% de
los casos. En cambio la búsqueda dicotómica sí que permite buscar los
elementos "desde x hasta y" (es decir, con un cierto prefijo), y garantiza
encontrar el primer resultado con un máximo de log2(n) accesos, y los
siguientes resultados con 1 único acceso adicional.