Estructuras de datos importantes en la búsqueda

Question

Me interesa enseñarme diferentes estructuras de datos, algo de lo que actualmente sé muy poco. Mi plan es implementar algunas estructuras clave para entender cómo funcionan. Estoy buscando sugerencias sobre estructuras de datos importantes para empezar.

Me interesan principalmente las estructuras de datos que son relevantes para las aplicaciones de búsqueda (por ejemplo, Google/Lucene) y la compensación general entre el cálculo retrasado y la precomputación. También me interesan las estructuras distribuidas de datos (estructuras de datos que pueden escalar a través de cientos/miles de servidores) y estructuras de datos probabilísticos, estructuras de datos que ayudan a encontrar una respuesta aproximada, pero que no necesitan ser siempre correctas.

Wikipedia tiene un list of data structures. Actualmente estoy considerando:

• tabla hash
• árbol B +
• R-Tree
• KD-árbol
• Radix-árbol
• Bloom filtrar

¿Hay mejores opciones?

Finalmente, ¿hay algún problema (mayor) al implementar estas estructuras en un lenguaje como F #?

Answer 1

Muy ambicioso. He votado su pregunta solo por su alcance.

MIT tiene un on-line algorithms and data structures course. El companion book es un clásico. No estoy seguro de si aborda las características distribuidas y probabilísticas, pero te darán una excelente base en los fundamentos.

Agregaría árbol rojo-negro, tablas hash, patricia trie y listas de omisiones a su agenda.

Buena suerte.

Answer 2

Dado que tiene muy poco conocimiento sobre DS, creo que debería comenzar con las listas (listas simples y doblemente vinculadas).

Luego puede estudiar diversas estructuras de datos de árbol.

Además, como está interesado en DS relacionado con la búsqueda, creo que debería estudiar B-tree + trees y hash table.

The Algorithm Design Manual es un buen libro para aprender más sobre algoritmos.

Answer 3

Para la búsqueda, los algoritmos son más importantes que las estructuras de datos. Al buscar en un gran espacio de búsqueda, a menudo debe tener métodos sofisticados para podar el espacio de búsqueda.

Puede consultar algoritmos de búsqueda clásicos como alfa-beta, A *, AO *.

Luego, observe algo así como la búsqueda de profundización iterativa.

En algoritmos de búsqueda, cosas como pilas y listas vinculadas (que son realmente una forma de una pila) y árboles son más importantes que las tablas hash, B-trees etc. Por supuesto, sin duda tendrá tablas hash allí, pero no será el corazón del algoritmo.

Aquí hay más importante algorithsm búsqueda:

1. B * Búsqueda
2. dar marcha atrás
3. búsqueda en haz
4. mejor primera búsqueda
5. búsqueda bidireccional
6. búsqueda en escalada
7. recocido simulado
8. AIF *
9. profundización iterativa primero en profundidad de búsqueda
10. mini-max búsqueda
11. búsqueda del vecino más cercano
12. difusión de la activación
espacio de búsqueda
13. estado (no una técnica, sólo una forma de conceptualizar un problema) .

En lo que respecta a las estructuras de datos específicas para la búsqueda, realmente no necesita ninguna. Básicamente, solo necesita su conjunto de herramientas de estructuras de datos habitual: árboles, hashes, listas.

Answer 4

Si va a abordar este tipo de cosas con un lenguaje funcional, debe echar un vistazo a Estructuras de datos puramente funcionales de Chris Okasaki. La lección básica es: las estructuras de datos con las que está familiarizado para la programación imperativa pueden no ser las mejores opciones para la programación funcional. Espero que haya mucho material similar para buscar en Google.