¿Se siguen inventando nuevas estructuras de datos en informática? ¿Se están volviendo cada vez más complejos o podemos esperar encontrar estructuras de datos útiles, como una cola prioritaria?

Sí, en su mayoría se están volviendo cada vez más complejos, pero aún encontrará algunas bastante útiles entre las nuevas estructuras de datos desarrolladas recientemente, y también nuevas formas de hacer las cosas viejas de una manera más rápida / mejor / más simple.

Algunos ejemplos:

• En 2008, Sedgewick publicó el árbol rojo-negro de inclinación hacia la izquierda, un árbol RB con una implementación más simple.
• Contando los filtros Bloom introducidos por Fan et al. en 1998, aún se están desarrollando versiones mejoradas.
• Cuckoo hashing de Pagh y Rodler en 2001.
• Una construcción bastante simple (y rápida en la práctica) O (n) de la matriz Suffix y la matriz LCP por Nong, Zhang y Chan en 2009.
• En los últimos años se ha trabajado mucho en las estructuras de datos persistentes (es decir, las que se pueden consultar sobre su contenido en el pasado) y en las estructuras de datos sucintas (es decir, las estructuras de datos de modo que el espacio total utilizado por la estructura de datos está cerca del límite inferior teórico de la información)

Sí y no, dependiendo de cómo defina “nueva estructura de datos”. Por ejemplo, muchas personas considerarían la cola prioritaria como una cola, o incluso como una lista vinculada. Además, la cola de prioridad no es nueva. Creo que Bell Lab comenzó a usarlo en la década de 1970.

Si cree que B-tree es una nueva estructura de datos, entonces hay muchos miembros nuevos en la familia de árboles: P-tree, block P-tree, indexed block P-tree, … estos son bastante útiles para datos multidimensionales indexación.

Debería haberlo, aunque actualmente no tengo conocimiento de ninguno. El objetivo debe ser realizar todas las operaciones en O (1) y eso, por supuesto, debe significar que nuevas estructuras de datos continuarán apareciendo durante cientos de años hasta que se alcance ese objetivo.

Esa es la teoría, pero en la práctica me he conformado con Hashmaps porque de alguna manera pueden resolver casi todo y parecen ser la mejor estructura de datos de la historia. Si descuenta el cálculo de los códigos hash, los hashmaps son O (1) al crear, leer, actualizar, eliminar (CRUD).

Por ejemplo, puede implementar una tabla de base de datos con una tabla Hash. El PK es la clave y todo el registro es el valor.

Una operación que BTrees + puede realizar de manera muy eficiente es la búsqueda siguiente y anterior, por lo que si tiene un índice secundario y realiza una búsqueda utilizando ese índice, generalmente obtendrá un rango de filas.

Ese rango de filas se representa en el BTree + del índice secundario como se deja en la parte inferior del Btree +, por lo que la siguiente operación es obtener el siguiente elemento en la matriz que representa el nodo en el Btree +, y luego cuando te quedas sin elementos en Para esa matriz, necesita un puntero al siguiente nodo, que es una especie de punto de usar BTree + en lugar de Btree.

Resulta que simplemente puedo tener un Hashmap de la clave secundaria a una lista de PK en la tabla. Es más simple y no necesito crear estructuras de datos especiales que luego deba depurar.

Y si está calculando códigos hash, ya sabe cómo particionar sus datos en diferentes máquinas y reducir los mapas. Por lo tanto, parece que no se necesitan nuevas estructuras de datos a menos que pueda vencer a los hashmaps.

En el hardware actual, las matrices siempre superan las listas vinculadas.

Aparte de eso, la mayoría de los desarrolladores desconocen la tecnología bastante antigua:

1. Caché de algoritmos ajenos.
2. Estructuras de datos sin bloqueo.
3. Bucketort puede ordenar grandes matrices en O (n) y si lo hace en paralelo utilizando estructuras de datos sin bloqueo, puede hacerlo en O (n / p) donde p es el número de núcleos.
4. Los algoritmos y las estructuras de datos son secundarios para reducir el acceso al disco.
5. Java funciona más rápido que C debido a la recolección de basura. La compactación de memoria significa que malloc es más lento que nuevo.
6. Mínimo hashing perfecto.

Y hacer que el programa funcione y luego cambiar las implementaciones es mucho más importante que seleccionar el algoritmo o la estructura de datos correctos, estos deberían estar ocultos dentro de las bibliotecas.

El uso de pruebas unitarias (Junit) debería ser la primera preocupación. Elegir la estructura de datos correcta a mano debería ser un pensamiento secundario, y solo será posible si el código es lo suficientemente limpio como para poder tener diferentes implementaciones.

Muchas de las estructuras de datos se utilizaron principalmente en bases de datos.

Hoy en día, las bases de datos están distribuidas principalmente y orientadas a big data

Ejemplos:

1. Hash coherente para construir bases de datos nosql Hash coherente
2. Formas de almacenar grandes matrices / gráficos en un clúster de máquinas y ejecutar operaciones de manera eficiente en ellos (redes sociales, gráficos web).

Otra dirección en las estructuras de datos es aproximar los resultados, también muy relacionados con el tamaño de los datos en las aplicaciones modernas.

Ejemplos:

1. Hash LSH, proyección aleatoria, etc. Hash sensible a la localidad: se utiliza en muchos sistemas ML a gran escala como recomendaciones
2. Recuento distinto aproximado HyperLogLog

Una respuesta extensa para una versión detallada de esta pregunta (con respecto a las estructuras de datos puramente funcionales) está disponible en http://cstheory.stackexchange.co …

Para conocer varias estructuras de datos inventadas recientemente, consulte los materiales del taller en http://www.imsc.res.in/dsmeet?ti …

¡Seguro! En mi campo de especialización, se trata principalmente de estructuras de datos concurrentes, aquellas adecuadas para ejecutar múltiples hilos / solicitudes simultáneamente. Ni siquiera puedo contarlos todos, listas de omisión concurrentes, árboles, tablas hash, etc. También hay diferentes “grados” de concurrencia, cada uno de los cuales permite una estructura de datos diferente. Creo que cientos de nuevas estructuras de datos concurrentes se inventaron después del año 2010.

Todo lo que se necesita es un problema interesante, dar a luz una nueva estructura de datos.