Estructuras de datos avanzadas en la práctica

Question

En los 10 años que he estado programando, puedo contar la cantidad de estructuras de datos que he usado por un lado: matrices, listas vinculadas (estoy acumulando montones y haciendo colas con esto) y diccionarios. Esto no es realmente sorprendente dado que casi todas las aplicaciones que he escrito entran en la categoría de formularios sobre datos/CRUD.

Nunca he necesitado utilizar un árbol rojo-negro, lista de omisiones, cola de doble final, lista de enlaces circulares, cola de prioridad, montones, gráficos o cualquiera de las docenas de estructuras de datos exóticas que se han investigado en los últimos 50 años. Siento que me estoy perdiendo.

Esta es una pregunta abierta, pero ¿dónde se usan en la práctica estas estructuras de datos "exóticas"? ¿Alguien tiene alguna experiencia en el mundo real utilizando estas estructuras de datos para resolver un problema en particular?

Answer 1

Algunos ejemplos. Son vagos porque eran de trabajo para los empleadores:

• Un heap para obtener los mejores resultados N en una búsqueda de estilo Google. (Partiendo de los candidatos en un índice, hágalo de forma lineal, cribéjelos en un min-montón de tamaño máximo N.) Esto fue para un prototipo de búsqueda de imágenes.

• Bloom filters redujo el tamaño de ciertos datos sobre lo que millones de usuarios habían visto hasta una cantidad que encajaría en los servidores existentes (todo tenía que ser en RAM para la velocidad); el diseño original habría necesitado muchos servidores nuevos solo para esa base de datos.

• A triangular array representation redujo a la mitad el tamaño de una matriz simétrica densa para un motor de recomendación (RAM nuevamente por la misma razón).

• Los usuarios deben agruparse según ciertas asociaciones; union-find hizo esto fácil, rápido y exacto en lugar de lento, hacky y aproximado.

• Una aplicación para elegir los sitios de venta por menor de acuerdo con el tiempo de conducción para las personas en el vecindario utilizado Dijkstra shortest-path con colas de prioridad. Otros trabajos GIS aprovecharon los índices quadtrees y Morton.

Sabiendo lo que hay en estructuras de datos en tierra viene muy bien - "semanas en el laboratorio le puede ahorrar horas en la biblioteca". La carcasa del filtro de floración solo valía la pena debido a la escala: si el problema hubiera surgido en una startup en lugar de Yahoo, habría usado una tabla hash simple. Los otros ejemplos que creo que son razonables en cualquier lugar (aunque hoy en día es menos probable que los codifique usted mismo).

Answer 2

Depende del nivel de abstracción en el que trabaje.

Sé que tengo una experiencia similar a la tuya. En el nivel actual de abstracción de la mayoría del desarrollo de software. El diccionario y la lista son las principales estructuras de datos que utilizamos.

Creo que si observas el código de nivel inferior verás más estructuras de datos "exóticas".

Answer 3

A menudo se utilizan detrás de escena en las bibliotecas. Por ejemplo, una estructura de datos diccionario ordenado (es decir, un associative array que alows recorrido ordenado por teclas) es tan probable como para no ser implementado usando un red-black tree.

Muchas estructuras de datos (splay trees vienen a la mente) son interesantes por su comportamiento óptimo en cierta circunstancias (temporal locality of reference en el caso de árboles de cobertura), por lo que son principalmente relevantes para el uso en estos casos. En la mayoría de las circunstancias, el beneficio real de un conocimiento práctico de estas estructuras de datos es poder emplearlas en las circunstancias adecuadas con una comprensión razonable de su comportamiento.

clasificación Tomemos, por ejemplo:

• En la mayoría de las circunstancias quicksort o una quicksort modificado que cae a otro método cuando los segmentos individuales consiguen lo suficientemente pequeño es típicamente el algoritmo más rápido de clasificación para la mayoría propósitos. Sin embargo, la oferta rápida tiende a mostrar comportamiento por debajo del óptimo en datos casi ordenados.

• la ventaja principal de un heap sort es que se puede hacer en situ con un mínimo de almacenamiento intermedio, que hace que sea bastante bueno para su uso en la memoria limitada sistemas. Si bien es más lento en promedio (aunque sigue siendo n log (n)), no sufre del peor de los casos en el peor de los casos de quicksort.

• Un tercer ejemplo es un merge sort, lo cual puede hacerse secuencialmente, por lo que es la mejor opción para clasificar conjuntos de datos mucho más grande que su memoria principal. Otro nombre para esto es 'clasificación externa', lo que significa que puede ordenar utilizando almacenamiento externo (disco o cinta ) para obtener resultados intermedios.

Answer 4

B-trees están en bases de datos.

R-trees son para las búsquedas geográficas (por ejemplo, si tengo 10000 formas, cada uno con un cuadro delimitador dispersos alrededor de un plano 2-D, cuál de estas figuras se cruzan un cuadro delimitador arbitrario B?)

deques de la forma en el C++ STL son vectores cultivables (más eficiente en cuanto a la memoria que las listas enlazadas, y elementos arbitrarios de tiempo constante para "mirar" en el medio). Hasta donde puedo recordar, nunca he usado el deque en toda su extensión (insertar/eliminar desde ambos extremos) pero es lo suficientemente general como para usarlo como una pila (insertar/eliminar desde un extremo) o cola (insertar hasta un extremo, eliminar del otro) y también tener acceso de alto rendimiento para ver elementos arbitrarios en el medio.

Acabo de leer Java Generics and Collections - la parte "generics" me duele la cabeza, pero la parte de colecciones fue útil & señalan algunas de las diferencias entre las listas de omisiones y los árboles (ambos pueden implementar mapas/conjuntos): las listas de omisiones le brindan iteración de tiempo constante incorporada de un elemento al siguiente (los árboles son O (log n)) y son mucho más simples para implementar algoritmos sin bloqueo en situaciones de multiproceso.

Las colas de prioridad se utilizan para programar entre otras cosas (aquí hay un webpage que trata brevemente la aplicación); montones se utilizan generalmente para implementarlos. También descubrí que el heapsort (al menos para mí) es el más fácil de entender (O log n) para implementar.

Answer 5

Sí, a veces. El problema que veo es que varias personas, aunque las conocen, no saben cómo aplicarlas realmente. La mayoría de las personas vuelven a las listas de matrices vinculadas, etc. Lo harán en la mayoría de los casos como una estructura de datos más avanzada (a veces hay que "patearlo"), pero son menos eficientes. La gente tiende a hacer lo que es más fácil para ellos, pero no es necesariamente la mejor manera de hacer algo. No puedo culparlos, estoy seguro de que también lo hago, pero es por eso que no se ven muchos de los conceptos "avanzados" en programación.

Answer 6

I use ring buffers/circular queues constantly in embedded work to service interrupts (e.g. serial ports).

Tree structures are heavily used in computer graphics.

If you use STL map or set data structures, then you are probably using a red-black tree without even knowing it!

Answer 7

He utilizado las listas enlazadas circulares para implementar colas (en C) que voy a iterar para siempre, es decir, una cola de conexión de red.

Pero me parece que cuando uso lenguajes de nivel superior, no me molesto en implementar colas de esta manera, porque puedo crecer y reducir dinámicamente una lista sin preocuparme demasiado por ella. Por supuesto, hay un precio de rendimiento para esto, porque tengo menos control sobre cuándo ocurre la asignación de memoria, pero ese es uno de los precios que pagamos por poder tener listas muy flexibles.

Answer 8

Acabo de encontrar un uso para los gráficos haciendo una question en StackOverflow :)

Answer 9

Usted tiende a ver las estructuras de datos más complicadas cuando se está dictada por las necesidades del código. Por lo general, veré esto cuando se trata de un código más complejo en niveles más bajos, es deciren el sistema operativo central, escribir partes fundamentales de una biblioteca de clase (implementación de cadena, matriz, etc.), escribir código de ejecución extrema o multihilo, etc. El otro lugar en el que creo que juegan un papel importante es en la implementación de algoritmos específicos, la búsqueda , los algoritmos de muestreo, análisis estadístico, optimización, etc. a menudo se escriben teniendo en cuenta estructuras de datos particulares.

Answer 10

A menudo uso conjuntos, colecciones ordenadas (siempre mantengo sus elementos en orden ordenado, y apoyo la inserción rápida de elementos) y listas diferidas.

Answer 11

Creo que ve estructuras de datos sofisticadas utilizadas la mayoría de los algoritmos de nivel superior. El principal ejemplo que me viene a la mente es A * que usa un gráfico y una cola de prioridad implementados por un Heap.

Answer 12

En finanzas necesita usar un árbol para calcular el valor de un instrumento que depende de muchos otros valores dinámicos. Las hojas de cálculo tienen un árbol de dependencias similar, y los compiladores crean un árbol de sintaxis abstracto antes de traducir al código máquina.

Answer 13

Los árboles equilibrados (Rojo-negro, etc.) se utilizan generalmente en la implementación de un tipo de datos abstracto.

Sólo hay un número relativamente pequeño de tipos de datos abstractos, tales como

• lista
• mapa
• mapa ordenado
• mapa de múltiples
• ordenada mapa de múltiples
• cola de prioridad (que se parece mucho a un mapa múltiple ordenado)

Del mismo modo, un conjunto se parece mucho a un mapa, pero no necesita los valores, solo las claves.

He encontrado la mayoría de estos útiles de vez en cuando; una cola de prioridad es una estructura de datos muy útil y tiene aplicaciones en todo tipo de algoritmos (por ejemplo, programación, búsqueda de ruta, etc.).

Dijiste "Diccionario", probablemente querías decir un mapa o un mapa ordenado.

Algunos mapas no están ordenados (normalmente se implementan como un hash): este es un subconjunto útil de un mapa ordenado.

Answer 14

Fibonacci heaps se utilizan para implementaciones eficientes de Dijkstra's algorithm.