type tad structures geeksforgeeks datastructures data all language-agnostic data-structures computer-science

language agnostic - tad - ¿Cuáles son las estructuras de datos menos conocidas pero útiles?



linear data structures (30)

<zvrba> árboles de Van Emde-Boas

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

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

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

Todo el mundo conoce las listas enlazadas, los árboles binarios y los hashes, pero, por ejemplo, qué pasa con las listas Omitir y los filtros Bloom . Me gustaría saber 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 me interesan las técnicas como los 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 la parte superior solo con base en sus votos.

Árbol de Fenwick. Es una estructura de datos para contar la suma de todos los elementos en un vector, entre dos subíndices i y j. La solución trivial, precalcular la suma desde el inicio no permite actualizar un elemento (tiene que hacer un trabajo O (n) para mantenerse al día).

Fenwick Trees le permite actualizar y consultar en O (log n), y su funcionamiento es realmente genial y simple. Está realmente bien explicado en el artículo 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 O (log n) actualización y consulta. Me gusta enseñar primero el RQM y luego el Árbol Fenwick.

Árboles de la bola. 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 utilizan para encontrar vecinos más cercanos a un punto o para acelerar k-medias.

Aquí hay algunos:

  • Sufijo lo intenta. Útil para casi todos los tipos de búsqueda de cadenas ( ). Véase también matrices de sufijos; no son tan rápidos como los árboles de sufijos, pero son mucho más pequeños.

  • Árboles repartidos (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 tamaño de nodo o color)
    • 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 y registro es el que todos conocen). Ver

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

  • Un nicho uno son las listas de adyacencia para gráficos planares no dirigidos con consultas O (1) 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 grado máximo de 6. Elija un nodo de este tipo, coloque a sus vecinos en su lista de vecinos, elimínelo del gráfico y repare hasta que esté vacío. Cuando se le presente 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, por lo que este es O (1).

Por 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 faltantes de cada nodo a la lista de vecinos de ese nodo, pero almacene la cantidad de la lista de vecinos que necesita consultar para una búsqueda rápida.

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 Union y Find resulta en costos amortizados que son efectivamente constantes (inverso a la función de Ackermnan, si recuerdo la clase de estructuras de datos correctamente).

Creo que las alternativas sin bloqueo a las estructuras de datos estándar, es decir, la cola sin bloqueo, la pila 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 es un objetivo mucho más admirable que usar Mutexes o bloqueos para manejar las 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) tiene algunos artículos excelentes sobre diseño y enfoques sin trabas

Cualquier persona con experiencia en renderización 3D debe estar familiarizada con los árboles BSP . Generalmente, es el método estructurando una escena 3D para que sea manejable para renderizar el conocimiento de las coordenadas de la cámara y el rumbo.

La partición de espacio binario (BSP) es un método para subdividir recursivamente un espacio en conjuntos convexos por 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 de espacio, vea partición de espacio.

Originalmente, este enfoque se propuso en gráficos de computadora en 3D para aumentar la eficiencia de representación. Algunas otras aplicaciones incluyen realizar 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 de computadora que involucran el manejo de escenas espaciales complejas.

Eche un vistazo a Finger Trees , especialmente si es un fanático de las 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 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 un ejemplo 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 de deque implícita, reemplazando pares con 2-3 nodos para proporcionar la flexibilidad requerida para una concatenación y división eficientes.

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

Es bastante específico del dominio, pero la estructura de datos de medio borde 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.

Me gusta caché Oblivious datastructures . La idea básica es colocar un árbol en bloques recursivamente más pequeños para que las cachés de muchos tamaños diferentes aprovechen los bloques que se ajustan cómodamente a ellos. Esto lleva a un uso eficiente del almacenamiento en caché en todo, desde el caché L1 en la 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é.

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.

No es realmente una estructura de datos; es más una forma de optimizar las matrices asignadas dinámicamente, pero los búferes de separación utilizados en Emacs son geniales.

Una variante interesante de la tabla hash se llama Cuckoo Hashing . Utiliza múltiples funciones de hash en lugar de solo 1 para hacer frente a las colisiones de hash. Las colisiones se resuelven eliminando el objeto antiguo de la ubicación especificada por el hash principal 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 tener un buen tiempo de acceso.

Bootstrapped skew-binomial heaps 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 requiere O(1) lugar de O(log n) tiempo, a diferencia de los montones más conocidos que generalmente se cubren en los libros de texto de estructura de datos, como los montones de izquierda . Y, a diferencia de los montones de Fibonacci , esos asintóticos son el peor de los casos, en lugar de amortizarse, incluso si se utilizan de forma persistente.

Hay multiple implementations en Haskell.

Fueron derivados conjuntamente por Brodal y Okasaki, después de que Brodal propusiera un montón imperativo con los mismos asintóticos.

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

Para agregar un elemento, ejecútelo mediante k funciones hash que le darán k índices en la matriz que luego configuró en 1.

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

Por supuesto, esto da 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 recuento del filtro de floración , representado por una matriz de entradas e incrementar / disminuir.

Fibonacci montones

Se usan en algunos de los algoritmos conocidos más rápidos (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. Desafortunadamente, sin embargo, tienen un alto factor constante, lo que a menudo los hace imprácticos en la práctica.

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

Rope : es una cadena que permite los antepuntos, subcadenas, inserciones medias y anexos baratos. Realmente solo lo he usado una vez, pero ninguna otra estructura hubiera sido suficiente. Las secuencias de comandos y los arreglos regulares eran demasiado caros para lo que teníamos que hacer, y revertir todo estaba fuera de discusión.

Saltar las listas son bastante ordenadas.

Wikipedia
Una lista de omisión es una estructura de datos probabilística, basada en varias listas enlazadas paralelas y ordenadas, con una eficiencia comparable a la de un árbol de búsqueda binario (registro de pedidos y 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 todos los buenos programadores.

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

Además, here hay un applet de Java que muestra las Listas de Salto visualmente.

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

Los arrays de bits almacenan bits individuales de forma compacta y permiten operaciones de bits rápidas.

Izquierda Inclinada árboles rojo-negro . 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 envolver su cabeza alrededor de la implementación de un árbol Rojo-Negro, lea acerca de esta variante.

Muy similar (si no es idéntico) a los árboles de Andersson.

Zippers : 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 los indicios no pueden estar fuera de límite, por ejemplo, en el administrador de ventanas de xmonad para rastrear qué ventana se ha enfocado.

Sorprendentemente, puede derivarlas aplicando técnicas de cálculo al tipo de estructura de datos original.

  • KD-trees , la estructura de datos espaciales utilizada (entre otros) en el Raytracing en tiempo real, tiene la desventaja de que los triángulos que se cruzan se intersecan con los diferentes espacios que deben recortarse. Generalmente 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 hash jerárquico con tiempos de acceso que generalmente superan los mapas hash O (1) 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, si no todos, de estos están documentados en el Diccionario NIST de Algoritmos y Estructuras de Datos