¿Qué puede decir acerca de las estructuras de datos modernas? Todos conocemos los clásicos, como árboles, intentos, stacks, listas, B-trees, etc. (creo que el libro de Cormen es una lista bastante buena de "clásicos"). ¿Pero qué hay de las investigaciones recientes? Puedo nombrar al menos 2 de ellos: finger trees y judy arrays. Me gustaria saber mas.Estructuras de datos de última generación
Eso realmente depende de su definición de "reciente". El CLRS contiene una gran cantidad de estructuras de datos, pero omite muchas de las estructuras que se habían desarrollado en ese momento. Por ejemplo, el árbol de van Emde Boas, que permite el almacenamiento extremadamente rápido y la búsqueda de enteros, se había desarrollado en ese momento, pero no se menciona en ninguna parte.
Una gran parte de la investigación moderna ha estado en las estructuras de datos de memoria caché, que son estructuras que aprovechan la jerarquía de la memoria de forma óptima sujeto a ciertas suposiciones razonables. Brodal es un investigador en este campo que ha producido muchas estructuras excelentes de este tipo.
Las estructuras de datos puramente funcionales que se pueden utilizar en lenguajes funcionales (o en lenguajes imperativos para garantizar la persistencia) también son un tema activo de investigación. El trabajo de Chris Okasaki en este campo ha llevado a desarrollos de árboles nuevos y colas de prioridad, por ejemplo.
Las estructuras de datos distribuidos son de gran importancia actualmente. BigTable de Google es un gran ejemplo. De forma similar, las estructuras de datos concurrentes o sin bloqueo han encontrado su camino en muchos lenguajes de programación (ver, por ejemplo, ConcurrentHashMap de Java o CopyOnWriteArrayList).
Las estructuras de datos basadas en la amortización se mencionan tangencialmente en CLRS, que se centra en el montón de Fibonacci. Sin embargo, las estructuras de árbol desplegable y de acumulación asimétrica que también se desarrollaron en la misma época no se mencionan, aunque hoy son de gran importancia.
Las estructuras probabilísticas como la lista de sugerencias y la lista de omisiones han tenido mucha actividad de investigación, y son un gran lugar para seguir explorando. En una línea relacionada, sin duda vale la pena investigar mesas hash potentes como la tabla hash de cuco o tablas hash dinámicas y perfectas.
Las estructuras de datos para la geometría computacional han tenido un aspecto de enfoque en los últimos años, aunque lamentablemente no las conozco, lo suficiente como para sugerir estructuras particulares.
Las estructuras de datos para el procesamiento de cadenas, a saber, el árbol de sufijos, son extremadamente relevantes en la biocomputación y las búsquedas web. No creo que el CLRS siquiera mencione su existencia. Sin embargo, definitivamente debes analizarlos, ya que son responsables de gran parte del nuevo trabajo en genómica.
Muchos investigadores se han esforzado en construir estructuras de datos que aprovechen el hecho de que las máquinas modernas pueden operar en múltiples bits en paralelo.Algunas estructuras como el árbol de fusión, el árbol exponencial o el árbol Y-Fast explotan estas propiedades para ordenar y buscar en matrices de enteros más rápido que las barreras O (n lg n) impuestas en un modelo de comparación ingenuo.
También se está trabajando mucho en estructuras de datos de resúmenes, bocetos y sinopsis que intentan hacer posible responder preguntas sobre un conjunto de datos sin almacenar todo el conjunto explícitamente. El Count-Min sketch es un gran ejemplo de una de estas estructuras de datos.
Esto es sólo una pequeña muestra de las estructuras nuevas y frescas que hay. ¡Espero que sea un buen punto de partida!
respuesta :) Ni CopyOnWriteArrayList, ni ConcurrentHashMap es una estructura libre de bloqueo ConcurrentHashMap utiliza bloqueos eliminados (pero puede disminuir significativamente durante las llamadas virtuales de Object.equals()) y CopyOnWriteArrayList utiliza un único bloqueo en modificar. – bestsss
@ bestsss- Verdadero; Iba a buscar "estructuras concurrentes" en lugar de "estructuras sin cerrojo" cuando las describía. Esa fue una oración pobre de mi parte. – templatetypedef
CopyOnWriteArrayList no escala bien en absoluto (si tiene escritores) y ConcurrentHashMap no es tan bueno en sistemas verdaderamente multi-core (128+) (además de la semántica pobre de caching). – bestsss
Existen muchos cientos de estructuras de datos especializadas. http://en.wikipedia.org/wiki/List_of_data_structures es un buen comienzo.
Algunas de las innovaciones de la estructura de datos relativamente recientes (como en los últimos 30 años) han sido probabilísticas, como Skip Lists. Encuentro estos particularmente interesantes, pero no me mantengo al tanto de la investigación. La lectura reciente ACM Transactions on Algorithms puede ayudarlo a encontrar investigaciones interesantes y de vanguardia.
Pero, cualquier cosa "nueva" va a ser altamente especializada. Solo una vez en mucho tiempo se crea un algoritmo/estructura nuevo pero fundamentalmente importante (como listas, árboles, etc.).
cuco hash es un esquema en el programación informática para la resolución de hash colisiones de valores de funciones hash en una tabla. hashing cuco fue primero descrito por Rasmus Pagh y Flemming Friche Rodler en 2001.
http://en.wikipedia.org/wiki/Cuckoo_hashing
Entonces los frescos son: Cache-oblivious data structures
http://en.wikipedia.org/wiki/Kd -tree - references lo llevará a muchos más. Y http://xlinux.nist.gov/dads// – Anycorn
Esto es como preguntar por una versión moderna de una rueda, una sin esa antigua forma aburrida. – Cosmin
Puede encontrar algún material interesante en estas preguntas sobre SO sobre [avanzado] (http://stackoverflow.com/q/389216/211232), [complicado] (http://stackoverflow.com/q/559748/211232) y [cool] (http://stackoverflow.com/q/500607/211232) estructuras de datos. – WReach