796 votos

¿Qué son los menos conocidos pero útil de las estructuras de datos?

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

Todo el mundo sabe acerca de las listas enlazadas, árboles binarios, y hash, pero, ¿qué acerca de Saltarse las listas y filtros Bloom , por ejemplo. Me gustaría saber más de las estructuras de datos que no son tan comunes, pero que vale la pena conocer, ya que dependen de grandes ideas y enriquecer un programador de la caja de herramientas.

PS: yo también estoy interesado en técnicas como el Baile de los enlaces que hacer un uso inteligente de las propiedades de una común estructura de datos.

EDICIÓN: Por favor, intente incluir enlaces a páginas que describe las estructuras de datos con más detalle. También, trate de añadir un par de palabras sobre por qué una estructura de datos es cool (como Jonas Kölker ya se señaló). También, trate de proporcionar una estructura de datos por la respuesta. Esto permitirá que las mejores estructuras de datos a flotar en la parte superior basado en sus votos solo.

271voto

David Phillips Puntos 3413

Intenta, también conocido como prefijo-o árboles crit-bit árboles, han existido por más de 40 años, pero siguen siendo relativamente desconocido. Un muy interesante uso de intentos que se describe en "BASURA - UNA dinámica LC-trie y el hash de la estructura de datos", que combina un trie con una función de hash.

231voto

albwq Puntos 1215

Bloom filter: Bits de la matriz de m bits, inicialmente todos los set a 0.

Para agregar un elemento de ejecutar a través de k funciones de hash que le dará k los índices de la matriz que a continuación se establece en 1.

Para comprobar si un elemento está en el conjunto, calcular el k índices y comprobar si están todos a 1.

Por supuesto, esto da una probabilidad de falsos positivos (según wikipedia se trata de 0.61^(m/n), donde n es el número de elementos que insertemos). Falso-negativos no son posibles.

La eliminación de un elemento es imposible, pero se puede aplicar a contar bloom filtro, representado por la matriz de enteros y de incremento/decremento.

140voto

Patrick Puntos 20392

Cuerda: Es una cadena que permite turístico, se antepone, subcadenas, medio inserciones y anexa. He tenido sólo uso para ello de una vez, pero ninguna otra estructura habría bastado. Regular las cadenas y matrices, se antepone eran simplemente demasiado caro para lo que teníamos que hacer, y revertir todo lo que estaba fuera de la cuestión.

128voto

Simucal Puntos 34961

Saltar listas son bastante limpio.

Wikipedia
Un salto lista es probabilística estructura de datos, basado en múltiples paralelas, que se ordenan las listas enlazadas, con una eficiencia comparable a la de un árbol de búsqueda binario (orden de registro n tiempo promedio para la mayoría de las operaciones).

Pueden ser utilizados como una alternativa a los árboles de equilibrado (usando probalistic equilibrio lugar de aplicación estricta de la ley de equilibrio). Son fáciles de aplicar y más rápido que, por ejemplo, un árbol rojo-negro. Creo que debería ser en todos los buenos programadores toolchest.

Si desea obtener una introducción detallada a saltarse las listas de aquí es un enlace a un vídeo de MIT Introducción a los Algoritmos conferencia sobre ellos.

También, aquí es un applet de Java que demuestra Saltar Listas visualmente.

92voto

Yuval F Puntos 15248

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

Matrices de bits de la tienda de bits individuales de forma compacta y permitir una rápida bits operaciones.

Iteramos.com

Iteramos es una comunidad de desarrolladores que busca expandir el conocimiento de la programación mas allá del inglés.
Tenemos una gran cantidad de contenido, y también puedes hacer tus propias preguntas o resolver las de los demás.

Powered by:

X