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

Existen algunas estructuras de datos que son realmente útiles, pero son desconocidas para la mayoría de los progtwigdores. ¿Cuáles son?

Todo el mundo sabe acerca de listas enlazadas, árboles binarios y hash, pero ¿qué pasa con las listas Omitir y los filtros Bloom, por ejemplo? Me gustaría saber más estructuras de datos que no son tan comunes, pero vale la pena conocerlas porque confían en grandes ideas y enriquecen la caja de herramientas de un progtwigdor.

PD: También estoy interesado en técnicas como enlaces de baile 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 ya señaló Jonas Kölker ). Además, trate de proporcionar una estructura de datos por respuesta . Esto permitirá que las mejores estructuras de datos floten hacia arriba en función de sus votos solamente.

Las pruebas , también conocidas como árboles de prefijos o árboles críticos , existen desde hace más de 40 años, pero aún son relativamente desconocidas. Un uso muy bueno de los bashs se describe en ” BASURA – Una estructura de datos LC-trie y hash dinámica “, que combina un trie con una función hash.

Filtro Bloom : matriz de bits de m bits, inicialmente todo configurado en 0.

Para agregar un elemento, ejecute k funciones hash que le darán k índices en la matriz que luego configurará en 1.

Para verificar si un artículo está en el conjunto, calcule los índices k y verifique si están todos configurados en 1.

Por supuesto, esto da una cierta probabilidad de falsos positivos (según wikipedia es de aproximadamente 0.61 ^ (m / n) donde n es el número de elementos insertados). Los falsos negativos no son posibles.

La eliminación de un elemento es imposible, pero puede implementar el filtro de conteo de bloom , representado por un conjunto de entradas y un incremento / disminución.

Cuerda : es una cuerda que permite prepuntas, subcadenas, inserciones medias y anexos baratas. Realmente solo lo he usado una vez, pero ninguna otra estructura hubiera sido suficiente. Las cadenas y arreglos regulares antes eran demasiado caros para lo que necesitábamos hacer, y anular todo estaba fuera de discusión.

Las listas de omisiones son bastante claras.

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

Se pueden utilizar como una alternativa a los árboles equilibrados (utilizando el equilibrio probalístico en lugar de la aplicación estricta de equilibrio). Son fáciles de implementar y más rápidos que, por ejemplo, un árbol rojo-negro. Creo que deberían estar en todos los buenos toolters de progtwigdores.

Si desea obtener una introducción en profundidad a las listas de omisiones, aquí hay un enlace a un video de la conferencia Introducción a los Algoritmos del MIT.

Además, aquí hay un applet de Java que muestra Skip Lists visualmente.

Los índices espaciales , en particular árboles R y árboles KD , almacenan datos espaciales de manera eficiente. Son buenos para los datos de coordenadas cartográficas geográficas y los algoritmos de lugar y ruta VLSI, y en ocasiones para la búsqueda de vecinos más cercanos.

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

Cremalleras : derivados 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 límite, por ejemplo, en el administrador de ventanas xmonad para rastrear qué ventana se ha enfocado.

Sorprendentemente, puedes derivarlos aplicando técnicas del cálculo al tipo de la estructura de datos original.

Aquí hay algunos:

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

  • Árboles de Splay (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 toda una serie de “criterios de medición” (el tiempo de búsqueda de log es el que todo el mundo conoce). Ver http://en.wikipedia.org/wiki/Splay_tree#Performance_theorems
  • Árboles de búsqueda ordenados en 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 stack con respecto a las prioridades. Se puede demostrar que dicho árbol tiene una forma única (y no siempre está completamente empaquetado arriba y a la izquierda). Con prioridades aleatorias, le da el tiempo de búsqueda O (log n) esperado, IIRC.

  • Un nicho es listas de adyacencia para gráficos planares no dirigidos con O (1) consultas vecinas. 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 máximo de 6. Elija un nodo, coloque sus vecinos en su lista de vecinos, elimínelos del gráfico y repita hasta que el gráfico esté vacío. Cuando se le dé un par (u, v), busque la lista de vecinos de v y la lista de vecinos de v en su. Ambos tienen un tamaño máximo de 6, por lo que este es O (1).

Con el algoritmo anterior, si u y v son vecinos, no tendrá ni u en la lista de v ni v en su lista. Si necesita esto, simplemente agregue los vecinos faltantes de cada nodo a la lista de vecinos de ese nodo, pero almacene la cantidad de la lista de vecinos que necesita revisar para una búsqueda rápida.

Creo que las alternativas sin locking a las estructuras de datos estándar, es decir, la cola libre de lockings, la stack y la lista, 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 objective mucho más admirable que usar Mutexes o lockings 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 a PDF]
http://www.boyet.com/Articles/LockfreeStack.html

El blog de Mike Acton (a menudo provocativo) contiene algunos artículos excelentes sobre el diseño y los enfoques sin cerraduras

Creo que Disjoint Set es bastante ingenioso para los casos en los que necesitas dividir un grupo de elementos en conjuntos distintos y consultar la membresía. Una buena implementación de las operaciones de unión y búsqueda da como resultado costos amortizados que son efectivamente constantes (al contrario de la función de Ackermann, si recuerdo correctamente la clase de estructura de datos).

Montones de Fibonacci

Se usan en algunos de los algoritmos más rápidos conocidos (de manera asintótica) 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; usar montones de Fibonacci lo mejora a O (E + V log V), que es una gran aceleración para gráficos densos. Desafortunadamente, sin embargo, tienen un alto factor constante, a menudo haciéndolos poco prácticos en la práctica.

Cualquiera con experiencia en renderización 3D debería estar familiarizado con los árboles BSP . En general, es el método mediante la estructuración de una escena en 3D para ser manejable para la representación sabiendo las coordenadas de la cámara y el rumbo.

La partición del espacio binario (BSP) es un método para subdividir recursivamente un espacio en conjuntos convexos por hiperplanes. 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 angularjs no reflections (angularjs menores de 180 °). Para una descripción más general de la partición del espacio, consulte la partición del espacio.

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

Árboles Huffman : utilizados para la compresión.

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

Según el artículo original :

Nuestros 2-3 árboles de dedo funcionales 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 deque implícita, reemplazando pares con 2-3 nodos para proporcionar la flexibilidad requerida para la concatenación y división eficiente.

Un Finger Tree 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.

Buffer circular o de anillo : utilizado para transmitir, entre otras cosas.

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

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

Árboles de Van Emde-Boas

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

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

¿Qué tal splay trees ?

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

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

Un montón mínimo-máximo es una variación de un montón que implementa una cola de prioridad de doble extremo. Esto se consigue mediante un simple cambio en la propiedad de 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 comenzando desde 1.

http://sofes.miximages.com/data-structures/heap8.jpg

Me gustan las estructuras de datos de Cache Oblivious . La idea básica es diseñar un árbol en bloques recursivamente más pequeños para que los cachés de muchos tamaños diferentes aprovechen los bloques que se ajusten convenientemente en ellos. Esto lleva a un uso eficiente del almacenamiento en caché en todo, desde caché L1 en RAM hasta grandes fragmentos de datos leídos del disco sin la necesidad de conocer los detalles de los tamaños de cualquiera de esas capas de almacenamiento en caché.

Left Leaning Red-Black Trees . Una implementación significativamente simplificada de árboles rojo-negro por Robert Sedgewick publicada en 2008 (~ la mitad de las líneas de código para implementar). Si alguna vez ha tenido problemas para familiarizarse con la implementación de un árbol Rojo-Negro, lea sobre esta variante.

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

Trabajo robando cola

Estructura de datos sin locking para dividir la igualdad de trabajo entre varios hilos Implementación de una cola de robo de trabajo en C / C ++?

Bootstrapped skew-binomial montones por Gerth Stølting Brodal y Chris Okasaki:

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

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

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

Hay múltiples implementaciones en Haskell.

Fueron derivados conjuntamente por Brodal y Okasaki, luego de que Brodal presentara un montón imperativo con las mismas características asintóticas.

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

La mayoría, sino todas, de estas están documentadas en el Diccionario de algoritmos y estructuras de datos del NIST.

Ball Trees. 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-means.

No es realmente una estructura de datos; una manera más de optimizar las matrices asignadas dinámicamente, pero los búferes de huecos usados ​​en Emacs son geniales.

Fenwick Tree. Es una estructura de datos para contar la sum de todos los elementos en un vector, entre dos subíndices dados i y j. La solución trivial, el precalculo de la sum desde el comienzo no permite actualizar un elemento (debe hacer O (n) para mantener el ritmo).

Fenwick Trees le permite actualizar y consultar en O (log n), y cómo funciona es realmente genial y simple. Está muy 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 genial: te 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 en C ++ de él, para hasta 2 ^ 20 enteros.

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

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