Pregunta ¿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 programadores. ¿Cuáles son?

Todo el mundo sabe sobre listas enlazadas, árboles binarios y hashes, pero ¿qué pasa con Omitir listas y 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 programador.

PD: también estoy interesado en técnicas como Bailando enlaces que hacen un uso inteligente de las propiedades de una estructura de datos común.

EDITAR: Por favor intente incluir enlaces a las páginas que describen las estructuras de datos en más detalle. Además, intente agregar un par de palabras en por qué una estructura de datos es genial (como Jonas Kölker ya señalado). 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.


797


origen


Respuestas:


Intentos, también conocidos como prefix-trees o árboles crit-bit, han existido por más de 40 años, pero aún son relativamente desconocidos. Se describe un uso muy bueno de tries en "BASURA: una estructura de datos LC-trie y hash dinámica", que combina un trie con una función hash.


271



Filtro Bloom: Matriz de bits de metro bits, inicialmente todo configurado en 0.

Para agregar un elemento lo ejecuta a través k funciones hash que te darán k índices en la matriz que luego establece en 1.

Para verificar si un artículo está en el conjunto, calcule el k índices y comprobar si están todos 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 contando el filtro de floración, representado por una matriz de ints e incremento / decremento.


231



Cuerda: Es una cadena que permite preprandiciones, subcadenas, inserciones intermedias 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.


140



Omitir listas son bastante aseados

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 programadores.

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

También, aquí es un applet de Java que muestra Skip Lists visualmente.


128



Índices espaciales, en particular R-trees y KD-trees, almacena 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.

Arrays de bits almacene bits individuales de manera compacta y permita operaciones rápidas de bits.


92



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: se usan, p. en el Administrador de ventanas xmonad para rastrear qué ventana se ha enfocado.

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


87



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 pila 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.


69



Creo que las alternativas sin bloqueo a las estructuras de datos estándar, es decir, la cola libre de bloqueos, 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 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 a PDF]
http://www.boyet.com/Articles/LockfreeStack.html 

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


65



creo Conjunto disjunto es bastante ingenioso para los casos en que necesitas dividir un grupo de elementos en conjuntos distintos y consultar 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).


55



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.


52