¿Cuáles son las estructuras de datos menos conocidas pero útiles?
Existen algunas estructuras de datos que son realmente útiles pero desconocidas para la mayoría de los programadores. ¿Cuales son?
Todo el mundo conoce las listas enlazadas, los árboles binarios y los hashes, pero ¿qué pasa con las listas de omisión y los filtros Bloom , por ejemplo? Me gustaría conocer más estructuras de datos que no son tan comunes, pero que vale la pena conocer porque se basan en grandes ideas y enriquecen la caja de herramientas de un programador.
PD: También estoy interesado en técnicas como los enlaces danzantes que hacen un uso inteligente de las propiedades de una estructura de datos común.
EDITAR : Intente incluir enlaces a páginas que describan las estructuras de datos con más detalle. Además, intente agregar un par de palabras sobre por qué una estructura de datos es interesante (como ya señaló Jonas Kölker ). Además, intente proporcionar una estructura de datos por respuesta . Esto permitirá que las mejores estructuras de datos lleguen a la cima basándose únicamente en sus votos.
Los intentos , también conocidos como árboles de prefijos o árboles de bits críticos , existen desde hace más de 40 años, pero aún son relativamente desconocidos. Un uso muy interesante de los intentos se describe en " BASURA: una estructura dinámica de datos LC-trie y hash ", que combina un trie con una función hash.
Filtro Bloom : matriz de bits de m bits, inicialmente todos configurados en 0.
Para agregar un elemento, lo ejecuta a través de k funciones hash que le darán k índices en la matriz que luego establecerá en 1.
Para verificar si un elemento está en el conjunto, calcule los índices k y verifique si todos están configurados en 1.
Por supuesto, esto da cierta probabilidad de falsos positivos (según Wikipedia, es aproximadamente 0,61 ^ (m/n) donde n es el número de elementos insertados). Los falsos negativos no son posibles.
Eliminar un elemento es imposible, pero puede implementar el filtro de conteo de floración , representado por una matriz de entradas e incremento/decremento.
Cuerda : Es una cadena que permite anteposiciones, subcadenas, inserciones intermedias y apéndices económicos. Realmente sólo lo he usado una vez, pero ninguna otra estructura hubiera sido suficiente. Los antepuestos de cadenas y matrices regulares eran demasiado costosos para lo que necesitábamos hacer, y revertir todo estaba fuera de discusión.
Las listas de omisión son bastante claras.
Wikipedia
Una lista de omisión es una estructura de datos probabilística, basada en múltiples listas vinculadas ordenadas y paralelas, con una eficiencia comparable a un árbol de búsqueda binario (registro de orden n tiempo promedio para la mayoría de las operaciones).
Se pueden utilizar como una alternativa a los árboles equilibrados (utilizando un equilibrio probalístico en lugar de una aplicación estricta del equilibrio). Son fáciles de implementar y más rápidos que, por ejemplo, un árbol rojo-negro. Creo que deberían estar en la caja de herramientas de todo buen programador.
Si desea obtener una introducción detallada a las listas de omisión, aquí hay un enlace a un video de la conferencia de Introducción a los algoritmos del MIT sobre ellas.
Además, aquí hay un subprograma de Java que demuestra visualmente las listas de omisión.
Los índices espaciales , en particular los árboles R y los árboles KD , almacenan datos espaciales de manera eficiente. Son buenos para datos de coordenadas de mapas geográficos y algoritmos de ruta y lugar VLSI y, a veces, para búsqueda de vecinos más cercanos.
Los Bit Arrays almacenan bits individuales de forma compacta y permiten operaciones rápidas de bits.
Feb 01 '2009 12:02