performance - sheet - data structures and algorithms in java course
¿Cuáles son las estructuras de datos complicadas de las que debería haber oído hablar? (14)
Agregaría Hash Tables a la lista. Son bastante simples en concepto, pero pueden ser complicados una vez que vea cómo implementar una buena función de hash y métodos de prueba eficientes.
Esta es una pregunta derivada, pero estoy indagando sobre las estructuras de datos con las que al menos debería estar familiarizado por su utilidad. Sin embargo, estas estructuras son demasiado difíciles de implementar sin cierta experiencia.
Yo diría que un buen límite entre los dos es un montón: debería poder codificar un montón, pero le tomaría un día. No es apropiado para esto sería una BST, etc. Edición: Veo el punto de que depende de lo que está haciendo. ¡Creo que sería increíble tener una lista con una frase que resuma por qué la usas!
Aquí hay una lista para comenzar:
- B + trees: buena estructura de indización general en una sola clave
- Árbol Kd: datos espaciales
- Árbol rojo-negro: BST autoequilibrante; también AVL o splay tree
- Omitir lista: buena estructura híbrida para el acceso aleatorio o (pseudo) secuencial
- Trie: búsqueda de cadenas de tiempo lineal
Este es un buen comienzo; hay una lista completa de estructuras de datos en wikipedia , algunas de ellas deben ser examinadas. Pero en cuanto a cuáles necesita, eso depende del área que pretenda ... hacer lo que sea que esté haciendo.
Los chicos de sistemas integrados tendrán ideas muy diferentes de los chicos de la web que estarán en total desacuerdo con los chicos de la lógica empresarial. Descubre lo que quieres hacer; los idiomas y la plataforma también afectarán la lista que necesita.
Estrechamente relacionado con el árbol B + que mencionaste: B * -ree . Junto con un enfoque de equilibrio conocido como el enfoque "árbol danzarín", estos forman la base de Reiser4.
Diagramas de decisión binarios , específicamente diagramas de decisión binarios de orden reducida (ROBDD). Estos se reinventan (poco) mucho cuando alguien decide crear su propio sistema de filtrado.
Hashing de cuckoo , una forma simple y elegante de resolver colisiones de tabla hash en el tiempo constante esperado.
Autómatas finitos deterministas (DFA), o máquinas de estados finitos , útiles para expresar muchas cosas, como lexers básicos, expresiones regulares, transiciones de estado, etc. Consulte también los gráficos de palabras acíclicas dirigidas relacionadas, que pueden ser útiles para almacenar diccionarios de forma compacta.
van Emde Boas árboles . Literalmente no creo que "deberías" haber oído hablar de ellos, pero sí creo que son un ejemplo interesante de qué tipo de complejidad puedes lograr con "trucos de bits", es decir, O (log log n), ¡exponencialmente mejor que los árboles binarios!
R-Tree y sus variantes, como R * -ree , X-Tree , Pyramid-Tree. Varias variantes de M-Tree, como Slim-Tree.
Como a menudo, consultar el árbol es fácil. También puede haber una carga masiva fácil (para R-Trees, STR a menudo hace un buen trabajo). La parte difícil suele ser el mantenimiento de un buen árbol en las actualizaciones.
Para citar a Martin Kay :
Los sufijos constituyen una estructura de datos bien comprendida, extremadamente elegante, pero lamentablemente poco apreciada, con potencialmente muchas aplicaciones (...)
Ver también: ¿Cuáles son las estructuras de datos menos conocidas pero interesantes?
Puedes probar:
- árboles y-fast
- Conjuntos ordenados aproximados
- seleccionar montón
- matrices compactas
- Listas monolíticas
- Listas sucinta