structures data book data-structures

data-structures - book - data structures types



Estructuras de datos avanzadas en la práctica (15)

A menudo se usan detrás de escena en las bibliotecas. Por ejemplo, una estructura de datos de diccionario ordenada (es decir, una matriz asociativa que permite el cruce ordenado por claves) es tan probable que no se implemente utilizando un árbol rojo-negro.

Muchas estructuras de datos (los árboles splay vienen a la mente) son interesantes para su comportamiento óptimo en ciertas circunstancias ( localidad de referencia temporal 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.

Tome la clasificación, por ejemplo:

  • En la mayoría de los casos, el quicksort o un quicksort modificado que se reduce a otro método cuando los segmentos individuales son lo suficientemente pequeños suele ser el algoritmo de clasificación más rápido para la mayoría de los propósitos. Sin embargo, quicksort tiende a mostrar un comportamiento subóptimo en datos casi ordenados.

  • La principal ventaja de una ordenación de almacenamiento dinámico es que puede realizarse in situ con un almacenamiento intermedio mínimo, lo que lo hace bastante bueno para su uso en sistemas con memoria limitada. Si bien es más lento en promedio (aunque sigue siendo n log (n)), no sufre el peor rendimiento en el peor de los casos de quicksort.

  • Un tercer ejemplo es un tipo de combinación , que se puede realizar de forma secuencial, por lo que es la mejor opción para ordenar conjuntos de datos mucho más grandes que la memoria principal. Otro nombre para esto es ''clasificación externa'', lo que significa que puede ordenar usando almacenamiento externo (disco o cinta) para obtener resultados intermedios.

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 enlazadas (estoy acumulando montones y 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óticos 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?

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

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

Algunos ejemplos. Son vagos porque eran trabajo para empleadores:

  • Un heap para obtener los N mejores resultados en una búsqueda al estilo de 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.

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

  • Una representación de matriz triangular 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 debían 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 sitios de venta minorista de acuerdo con el tiempo de conducción para las personas en el vecindario utilizó el camino más corto de Dijkstra con colas de prioridad. Otros trabajos de GIS aprovecharon los quadtrees y los índices de Morton .

Saber qué hay en data-structures-land es útil: "las semanas en el laboratorio pueden ahorrarle 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).

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.

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

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 miras hacia abajo al código de nivel inferior verás más estructuras de datos "exóticas".

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 sintáctico abstracto antes de traducir al código máquina.

He usado listas circulares vinculadas 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.

He usado una lista circular para el almacenamiento en caché.

Una plantilla de clase C ++ proporciona una interfaz para obtener objetos ( Cache<Obj, Len> ). Varias instatciones de él devuelven diferentes tipos de ''pantallas'' como en diferentes vistas de una interfaz gráfica. Detrás de las escenas, si la ''pantalla'' solicitada no está disponible, se crea (operación costosa) y se empuja hacia la cabeza del buffer de anillo, empujando la más antigua (descargando sus texturas, etc.).

Por lo tanto, se logra un compromiso entre leer siempre un montón de archivos de imagen del disco duro y simplemente cargar todas las imágenes en la memoria RAM y conservarlas para siempre. El compromiso está controlado por la longitud de los diversos búferes.

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

Solo hay un número relativamente pequeño de tipos de datos abstractos, como

  • lista
  • mapa
  • mapa ordenado
  • multi mapa
  • multi mapa ordenado
  • 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 hash); este es un subconjunto útil de un mapa ordenado.

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.

Tiende a ver estructuras de datos más complicadas cuando lo dictan las necesidades del código. Usualmente veré esto cuando se trata de código más complejo en niveles más bajos, es decir, en el sistema operativo central, escribiendo partes fundamentales de una biblioteca de clase (implementación de cadena, matriz, etc.), escriba código de ejecución extrema o código de múltiples subprocesos , etc. El otro lugar en el que creo que juegan un papel importante es en la implementación de algoritmos específicos, búsqueda, muestreo, análisis estadístico, optimización, etc. Los algoritmos a menudo se escriben con estructuras de datos particulares en mente.

B-trees están en bases de datos.

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

deques de la forma en 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 los genéricos y las colecciones de Java : la parte "genéricos" me duele, pero la parte de colecciones fue útil y señalan algunas de las diferencias entre las listas de omisiones y los árboles (ambos pueden implementar mapas / conjuntos): omitir las listas 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 multiproceso.

Las colas de prioridad se usan para programar entre otras cosas (aquí hay una webpage que discute 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.