¿Cuáles son las estructuras de datos menos conocidas pero útiles?

Existen algunas estructuras de datos que son realmente útiles pero que la mayoría de los programadores desconocen. ¿Cuáles son ellos?

Todo el mundo sabe sobre listas vinculadas, árboles binarios y 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 Dancing links 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 genial (como Jonas Kölker ya señaló). Además, intente proporcionar una estructura de datos por respuesta . Esto permitirá que las mejores estructuras de datos floten a la cima según sus votos solamente.

Los intentos , también conocidos como árboles de prefijo o árboles de bits críticos , han existido durante más de 40 años, pero aún son relativamente desconocidos. Un uso muy bueno de los intentos se describe en " TRASH - 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 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 establece en 1.

Para verificar si un elemento está en el conjunto, calcule el k índices y verifique si todos están establecidos en 1.

Por supuesto, esto da cierta probabilidad de falsos positivos (según wikipedia, se trata de 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 recuento de floración , representado por una matriz de entradas e incrementos / decrementos.

Cuerda : es una cadena que permite prepends, subcadenas, inserciones y anexos baratos. Realmente solo lo he usado una vez, pero ninguna otra estructura hubiera sido suficiente. Los preparativos de cadenas y matrices regulares eran demasiado caros para lo que necesitábamos hacer, y revertir todo estaba fuera de discusión.

Las listas de omisión son bastante ordenadas.

Wikipedia
Una lista de salto es una estructura de datos probabilística, basada en múltiples listas vinculadas paralelas y ordenadas, con una eficiencia comparable a un árbol de búsqueda binario (registro de pedidos en tiempo promedio para la mayoría de las operaciones).

Se pueden usar como una alternativa a los árboles equilibrados (usando el equilibrio probalístico en lugar de la aplicación estricta del equilibrio). Son fáciles de implementar y más rápidos que decir, un árbol rojo-negro. Creo que deberían estar en cada buen programador de herramientas.

Si desea obtener una introducción en profundidad 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 ellos.

Además, aquí hay un applet de Java que muestra visualmente las listas de omisión.

Índices espaciales , en particular, R-árboles y KD-árboles , almacenar datos espaciales de manera eficiente. Son buenos para los datos de coordenadas del mapa geográfico y los algoritmos de ruta y lugar VLSI, y a veces para la búsqueda del vecino más cercano.

Las matrices de bits almacenan bits individuales de forma compacta y permiten operaciones de bits rápidas.

Cremalleras : derivadas de estructuras de datos que modifican la estructura para tener una noción natural de 'cursor': ubicación actual. Estos son realmente útiles, ya que garantizan que las indicaciones no pueden estar fuera de uso, por ejemplo, en el administrador de ventanas xmonad para rastrear qué ventana se ha enfocado.

¡Sorprendentemente, puede derivarlos aplicando técnicas de cálculo al tipo de estructura de datos original!

Aquí hay algunos:

• El sufijo lo intenta. Útil para casi todo tipo de búsqueda de cadenas (http://en.wikipedia.org/wiki/Suffix_trie#Functionality ). Ver también arrays de sufijos; no son tan rápidos como los árboles de sufijos, pero son mucho más pequeños.

• Separe los árboles (como se mencionó anteriormente). La razón por la que son geniales es triple:

  • Son pequeños: solo necesita los punteros izquierdo y derecho como lo hace en cualquier árbol binario (no es necesario almacenar información de color o tamaño de nodo)
  • Son (comparativamente) muy fáciles de implementar
  • Ofrecen una complejidad amortizada óptima para una gran cantidad de "criterios de medición" (el tiempo de búsqueda es el que todos conocen). Verhttp://en.wikipedia.org/wiki/Splay_tree#Performance_theorems

• Árboles de búsqueda ordenados por montón: almacena un grupo de pares (clave, prio) en un árbol, de modo que es un árbol de búsqueda con respecto a las claves, y ordenado en montón con respecto a las prioridades. Se puede demostrar que dicho árbol tiene una forma única (y no siempre está completamente empaquetado hacia arriba y hacia la izquierda). Con prioridades aleatorias, le brinda el tiempo de búsqueda esperado de O (log n), IIRC.

• Un nicho es las listas de adyacencia para gráficos planos no dirigidos con consultas vecinas O (1). Esto no es tanto una estructura de datos como una forma particular de organizar una estructura de datos existente. Así es como lo hace: cada gráfico plano tiene un nodo con un grado máximo de 6. Seleccione un nodo de este tipo, coloque a sus vecinos en su lista de vecinos, retírelo del gráfico y repita hasta que el gráfico esté vacío. Cuando se le da un par (u, v), busque u en la lista de vecinos de v y v en la lista de vecinos de u. Ambos tienen un tamaño máximo de 6, así que este es O (1).

Según el algoritmo anterior, si u y v son vecinos, no tendrá tanto u en la lista de v como v en la lista de u. Si necesita esto, simplemente agregue los vecinos que faltan de cada nodo a la lista de vecinos de ese nodo, pero almacene la cantidad de la lista de vecinos que necesita para buscar rápidamente.

Creo que las alternativas sin bloqueo a las estructuras de datos estándar, es decir, la cola, la pila y la lista sin bloqueo, se pasan por alto.
Son cada vez más relevantes a medida que la concurrencia se convierte en una prioridad más alta y son un objetivo mucho más admirable que usar Mutexes o bloqueos para manejar lecturas / escrituras concurrentes.

Aquí hay algunos enlaces
http://www.cl.cam.ac.uk/research/srg/netos/lock-free/
http://www.research.ibm.com/people/m/michael/podc-1996.pdf [Enlaces al PDF]
http://www.boyet.com/Articles/LockfreeStack.html

El blog de Mike Acton (a menudo provocativo) tiene algunos artículos excelentes sobre diseño y enfoques sin bloqueo

Creo que Disjoint Set es bastante ingenioso para los casos en que necesita dividir un montón de elementos en conjuntos distintos y pertenecer a consultas. Una buena implementación de las operaciones Union y Find resulta en costos amortizados que son efectivamente constantes (inversa de la Función de Ackermnan, si recuerdo correctamente la clase de estructuras de datos).

Montones de Fibonacci

Se utilizan en algunos de los algoritmos más rápidos conocidos (asintóticamente) para muchos problemas relacionados con gráficos, como el problema de la ruta más corta. El algoritmo de Dijkstra se ejecuta en tiempo O (E log V) con montones binarios estándar; el uso de montones de Fibonacci mejora eso a O (E + V log V), que es una gran aceleración para gráficos densos. Sin embargo, desafortunadamente tienen un factor constante alto, lo que a menudo los hace poco prácticos en la práctica.

Cualquier persona con experiencia en renderizado 3D debe estar familiarizado con los árboles BSP . Generalmente, es el método al estructurar una escena 3D para que sea manejable para renderizar conociendo las coordenadas y la orientación de la cámara.

La partición de espacio binario (BSP) es un método para subdividir recursivamente un espacio en conjuntos convexos mediante hiperplanos. Esta subdivisión da lugar a una representación de la escena por medio de una estructura de datos de árbol conocida como árbol BSP.

En otras palabras, es un método para dividir polígonos de formas intrincadas en conjuntos convexos, o polígonos más pequeños que consisten completamente en ángulos no reflejos (ángulos menores de 180 °). Para una descripción más general de la partición espacial, vea partición espacial.

Originalmente, este enfoque se propuso en gráficos 3D por computadora para aumentar la eficiencia de representación. Algunas otras aplicaciones incluyen la realización de operaciones geométricas con formas (geometría sólida constructiva) en CAD, detección de colisiones en robótica y juegos de computadora en 3D, y otras aplicaciones informáticas que involucran el manejo de escenas espaciales complejas.

Árboles Huffman : utilizados para la compresión.

Echa un vistazo a Finger Trees , especialmente si eres fanático de estructuras de datos puramente funcionales mencionadas anteriormente . Son una representación funcional de secuencias persistentes que admiten el acceso a los extremos en tiempo constante amortizado, y la concatenación y división en tiempo logarítmico en el tamaño de la pieza más pequeña.

Según el artículo original :

Nuestros árboles funcionales de 2-3 dedos son una instancia de una técnica de diseño general introducida por Okasaki (1998), llamada desaceleración recursiva implícita . Ya hemos notado que estos árboles son una extensión de su estructura implícita de deque, reemplazando pares con 2-3 nodos para proporcionar la flexibilidad requerida para una concatenación y división eficiente.

Un árbol de dedos se puede parametrizar con un monoide , y el uso de diferentes monoides dará como resultado diferentes comportamientos para el árbol. Esto permite que Finger Trees simule otras estructuras de datos.

Búfer circular o en anillo : se utiliza para la transmisión, entre otras cosas.

Me sorprende que nadie haya mencionado los árboles Merkle (es decir, Hash Trees ).

Se utiliza en muchos casos (programas P2P, firmas digitales) donde desea verificar el hash de un archivo completo cuando solo tiene una parte del archivo disponible para usted.

<zvrba> Árboles Van Emde-Boas

Creo que sería útil saber por qué qué son geniales. En general, la pregunta "por qué" es la más importante de hacer;)

Mi respuesta es que le dan diccionarios O (log log n) con {1..n} claves, independientemente de cuántas claves estén en uso. Al igual que la reducción a la mitad repetida le da O (log n), el sqrting repetido le da O (log log n), que es lo que sucede en el árbol vEB.

¿Qué tal si se extienden los árboles ?

Además, me vienen a la mente las estructuras de datos puramente funcionales de Chris Okasaki .

Una variante interesante de la tabla hash se llama Cuckoo Hashing . Utiliza múltiples funciones hash en lugar de solo 1 para tratar las colisiones hash. Las colisiones se resuelven eliminando el objeto antiguo de la ubicación especificada por el hash primario y moviéndolo a una ubicación especificada por una función de hash alternativa. Cuckoo Hashing permite un uso más eficiente del espacio de memoria porque puede aumentar su factor de carga hasta un 91% con solo 3 funciones hash y aún así tener un buen tiempo de acceso.

Un montón min-max es una variación de un montón que implementa una cola de prioridad de doble extremo. Esto se logra mediante un simple cambio en la propiedad del montón: se dice que un árbol está ordenado min-max si cada elemento en niveles pares (impares) es menor (mayor) que todos los niños y nietos. Los niveles están numerados a partir del 1.

http://internet512.chonbuk.ac.kr/datastructure/heap/img/heap8.jpg

Me gusta Cache Oblivious datastructures . La idea básica es colocar un árbol en bloques recursivamente más pequeños para que los cachés de muchos tamaños diferentes aprovechen los bloques que encajan convenientemente en ellos. Esto lleva a un uso eficiente del almacenamiento en caché en todo, desde el caché L1 en RAM hasta grandes porciones de datos leídos del disco sin necesidad de conocer los detalles de los tamaños de cualquiera de esas capas de almacenamiento en caché.

Izquierda inclinada árboles rojo-negros . Una implementación significativamente simplificada de árboles rojo-negros por Robert Sedgewick publicada en 2008 (~ la mitad de las líneas de código para implementar). Si alguna vez ha tenido problemas para entender la implementación de un árbol Rojo-Negro, lea sobre esta variante.

Muy similar (si no idéntico) a Andersson Trees.

Cola de robo de trabajo

Estructura de datos sin bloqueo para dividir el trabajo equitativamente entre múltiples hilos Implementación de una cola de robo de trabajo en C / C ++?

Montones de binomio sesgado bootstrapped oblicuos de Bootstrapped por Gerth Stølting Brodal y Chris Okasaki:

A pesar de su nombre largo, proporcionan operaciones de almacenamiento dinámico asintóticamente óptimas, incluso en una configuración de función.

• O(1)tamaño, unión , inserto, mínimo
• O(log n) deleteMin

Tenga en cuenta que la unión toma O(1)más que O(log n)tiempo, a diferencia de los montones más conocidos que comúnmente se cubren en los libros de texto de estructura de datos, como los montones izquierdistas . Y a diferencia de los montones de Fibonacci , esos asintóticos son el peor de los casos, en lugar de amortizarse, ¡incluso si se usan de manera persistente!

Hay múltiples implementaciones en Haskell.

Fueron derivadas conjuntamente por Brodal y Okasaki, después de que a Brodal se le ocurrió un montón imperativo con los mismos síntomas.

• Kd-Trees , la estructura de datos espaciales utilizada (entre otros) en el trazado de rayos en tiempo real, tiene el inconveniente de que los triángulos que se cruzan intersectan los diferentes espacios deben recortarse. En general, los BVH son más rápidos porque son más livianos.
• MX-CIF Quadtrees , almacene cuadros delimitadores en lugar de conjuntos de puntos arbitrarios combinando un quadtree regular con un árbol binario en los bordes de los quads.
• HAMT , mapa de hash jerárquico con tiempos de acceso que generalmente exceden los mapas de hash O (1) debido a las constantes involucradas.
• Índice invertido , bastante conocido en los círculos de los motores de búsqueda, porque se utiliza para la recuperación rápida de documentos asociados con diferentes términos de búsqueda.

La mayoría, si no todos, están documentados en el Diccionario NIST de Algoritmos y Estructuras de Datos

Bola de árboles. Solo porque hacen reír a la gente.

Un árbol de bolas es una estructura de datos que indexa puntos en un espacio métrico. Aquí hay un artículo sobre cómo construirlos. A menudo se usan para encontrar vecinos más cercanos a un punto o acelerar k-medias.

No es realmente una estructura de datos; es una forma más de optimizar las matrices asignadas dinámicamente, pero los buffers de espacio utilizados en Emacs son geniales.

Fenwick Tree. Es una estructura de datos para mantener el recuento de la suma de todos los elementos en un vector, entre dos subíndices dados i y j. La solución trivial, precalculando la suma ya que el comienzo no permite actualizar un elemento (debe hacer O (n) para mantenerse al día).

Fenwick Trees le permite actualizar y consultar en O (log n), y cómo funciona es realmente genial y simple. Está realmente bien explicado en el documento original de Fenwick, disponible gratuitamente aquí:

http://www.cs.ubc.ca/local/reading/proceedings/spe91-95/spe/vol24/issue3/spe884.pdf

Su padre, el árbol RQM también es muy bueno: le permite mantener información sobre el elemento mínimo entre dos índices del vector, y también funciona en la actualización y consulta O (log n). Me gusta enseñar primero el RQM y luego el Fenwick Tree.

Árboles Van Emde-Boas . Incluso tengo una implementación de C ++ para hasta 2 ^ 20 enteros.

Los conjuntos anidados son buenos para representar árboles en las bases de datos relacionales y ejecutar consultas en ellos. Por ejemplo, ActiveRecord (ORM predeterminado de Ruby on Rails) viene con un complemento de conjunto anidado muy simple , lo que hace que trabajar con árboles sea trivial.

Es bastante específico de dominio, pero la estructura de datos de medio borde es bastante ordenada. Proporciona una forma de iterar sobre mallas poligonales (caras y bordes) que es muy útil en gráficos de computadora y geometría computacional.