¿Cuáles son las aplicaciones del mundo real de algunas estructuras de datos avanzadas, y cuándo elegiría una estructura de datos sobre otra, en el caso de estructuras de datos similares?

Cuerda : una estructura de datos relativamente menos enseñada en cursos de pregrado en ciencias de la computación. De acuerdo con wikipedia

Una soga , o soga , es una estructura de datos compuesta de cadenas más pequeñas que se utiliza para almacenar y manipular eficientemente una cadena muy larga.

Se usa ampliamente en programas de edición de texto. [1]

Me sorprende que nadie haya mencionado Fibonacci Heap creado por el famoso Tarjan. Es conocido por sus reducidas complejidades de tiempo amortizado que son mejores que los montones binomiales. [2] Se puede usar para hacer que Dijkstra sea más eficiente, lo que a su vez conduce a una optimización de red más eficiente. [3]

Solo he leído sobre Gap Buffer, que es una estructura de datos alternativa a las cuerdas. No he encontrado ninguna de sus implementaciones. Según la wiki, se usa en el editor de texto de Emacs. [4]

[1] Cuerda (estructura de datos)
[2] Montón de Fibonacci
[3] http://www.cs.princeton.edu/cour…
[4] Búfer de separación

• He utilizado estructuras de consulta de rango en una biblioteca de autocompletado del mundo real cpp-libface. Puede leer sobre cómo se usa aquí: Un enfoque muy rápido para autocompletar (o sugerencias de búsqueda).

• También estoy planeando usar un cruce entre un BIT y un árbol de segmentos (es decir, un árbol de segmentos binario [basado en bits]) para implementar listas libres de manera eficiente. Algunos pensamientos sobre tus (y mis) pensamientos.

• nessDB utiliza algunas estructuras de datos ajenas a la caché para implementar una indexación de memoria externa eficiente.

• El comando de clasificación de Unix utiliza la clasificación de memoria externa para ordenar la entrada utilizando una cantidad fija de memoria principal (RAM).

• bzip2 (o cualquier compresor basado en bloques) puede usar matrices de sufijos para localizar de manera eficiente regiones de superposición. Además, también utiliza la transformación Burrows – Wheeler para hacer que el texto sea más compresible.

• También he usado matrices de sufijos para calcular el delta entre 2 genomas. Genoma-Dif-Compresión.

• Visite http://www.cs.sunysb.edu/~rezaul … para ver un montón de técnicas que se pueden utilizar para acelerar en gran medida el cálculo de la distancia de edición (y, por lo tanto, la alineación del ADN) mediante el uso de una programación dinámica sin caché y eficiente en caché ( DP) técnicas. Aquí es donde DP se encuentra con Divide & Conquer.

• Mantenimiento de pedidos se utiliza en citas en línea 😀

Por supuesto, hay muchos más, pero estos son algunos que vienen a la mente de inmediato.

Gracias por el A2A.

Los árboles de sugerencias , que se basan en intentos , también se utilizan para implementar el autocompletado en aplicaciones más antiguas.

Los autómatas de Levenshtein se utilizan en la mayoría de las implementaciones de autocompletado en el mundo real: http://blog.notdot.net/2010/07/D… . (Ese blog, por cierto, tiene muchos otros ejemplos de algoritmos avanzados y estructuras de datos que se utilizan en el mundo real).

Los árboles rojo-negros se utilizan para implementar conjuntos ordenados en la mayoría de los lenguajes de programación. Por ejemplo, TreeSet en java y set en C ++ se implementan como árboles rojo-negro. La ventaja es que garantizan operaciones O (log (n)).

Los árboles B se utilizan para indexar datos en muchos sistemas de bases de datos como MySQL. La razón es que los árboles B son menos profundos que la mayoría de los otros tipos de árboles de equilibrio automático, por lo que reducen la cantidad de operaciones de disco necesarias para recuperar datos.

Esta respuesta habla de una estructura de datos específica para la tecnología de codificación de video.

La mayoría del codificador de video segrega los cuadros de entrada en bloques cuadrados de píxeles más pequeños, generalmente un múltiplo de 4 × 4 y luego los codifica uno por uno. Esto es cierto para todos los códecs de video. La mayoría de los estándares simplemente dividen el marco en bloques dependiendo de lo que cueste menos. Así es como se ve:

Aquí todos los bloques son del mismo tamaño, pero podría haber una mezcla de diferentes tamaños.

El estándar HEVC (codificación de video de alta eficiencia) o H.265 utiliza un esquema poco ortodoxo para dividir los cuadros en bloques. El marco se divide en bloques que podrían dividirse en subbloques más pequeños y lo mismo es cierto para los subbloques. Esto forma una estructura de bloques recursiva, o una estructura de cuatro árboles , de bloques cuadrados que cubren toda la imagen. El bloque más grande podría ser tan grande como 64 × 64 píxeles y el más pequeño podría ser tan pequeño como 4 × 4. Un buen codificador utiliza la estructura de bloques de cuatro árboles para teselar el marco de tal manera que el área fácil de decodificar tenga bloques no divididos más grandes y las áreas más finas tengan bloques divididos en subbloques que, dependiendo de qué tan dura sea una región de marco, podría dividirse en bloques más pequeños.

Así es como se ve:

El esquema de cuatro árboles es complicado pero da como resultado una mejor compresión sin comprometer la calidad del video.

Lecturas adicionales sobre Quad-tree: Quadtree
y en Hevc: codificación de video de alta eficiencia

* El blog Cómo el algoritmo de Kruskal usa la unión de conjuntos disjuntos para aplicaciones de la vida real se publicó en el blog HackerEarth *

La mayoría de las compañías de redes de cable utilizan la estructura de datos Disjoint Set Union en el algoritmo de Kruskal para encontrar el camino más corto para tender cables en una ciudad o grupo de ciudades.

Lo que nos lleva a esta publicación sobre las propiedades de Disjoint establece la unión y el árbol de expansión mínimo junto con sus aplicaciones de la vida real.

Antes de continuar con un ejemplo del algoritmo de Kruskal, primero comprendamos qué son los conjuntos disjuntos.

¿Qué son los conjuntos disjuntos?

Un conjunto disjunto es una estructura de datos que realiza un seguimiento de todos los elementos que están separados por una serie de subconjuntos disjuntos (no conectados). Con la ayuda de conjuntos disjuntos, puede realizar un seguimiento de la existencia de elementos en un grupo particular.

Digamos que hay 6 elementos A, B, C, D, E y F. B, C y D están conectados y E y F están emparejados. Esto nos da 3 subconjuntos que tienen elementos (A), (B, C, D) y (E, F).

Los conjuntos disjuntos nos ayudan a determinar rápidamente qué elementos están conectados y cercanos y a unir dos componentes en una sola entidad.

Una estructura de datos de conjunto disjunta consta de dos funciones importantes:

Find () : ayuda a determinar a qué subconjunto pertenece un elemento en particular.

También ayuda a determinar si el elemento está en más de un subconjunto.

Union () : ayuda a verificar si un gráfico es cíclico o no. Y ayuda a conectar o unir dos subconjuntos.

Implementación del conjunto disjunto

Para el ejemplo anterior, suponemos que para el conjunto (B, C, D), B es un nodo padre. Para el conjunto disjunto, mantenemos un representante único para cada nodo.

Si buscamos cualquier elemento en un nodo en particular, nos lleva al padre de ese nodo en particular.

Por lo tanto, cuando busque D, la respuesta sería B.

Del mismo modo, podemos conectar el subconjunto (A) a (E, F), lo que daría como resultado el nodo A como nodo principal.

Ahora tenemos dos subconjuntos, pero B y A no tienen ningún nodo padre. Cada árbol es un conjunto disjunto independiente, es decir, si dos o más elementos están en el mismo árbol, son parte del mismo conjunto disjunto, de lo contrario son independientes.

Entonces, si para un árbol particular B es un representante, entonces Parent [i] = B. Si B no es un representante, podemos mover el árbol hacia arriba para encontrar el padre o representante del árbol.

Puede leer más aquí sobre los conceptos básicos de conjuntos disjuntos.

Algoritmo de Kruskal

El árbol de expansión es la suma de los pesos de todos los bordes de un árbol. Un árbol de expansión mínimo (MST) es uno que cuesta menos entre todos los árboles de expansión.

Aquí hay un ejemplo de un árbol de expansión mínimo.

El algoritmo de Kruskal y el algoritmo de Prim son dos algoritmos populares para encontrar los árboles de expansión mínima.

El algoritmo de Kruskal utiliza el enfoque codicioso para encontrar un árbol de expansión mínimo. El algoritmo de Kruskal trata cada nodo como un árbol independiente y se conecta uno con otro solo si tiene el costo más bajo en comparación con todas las demás opciones disponibles.

Pasos del algoritmo de Kruskal:

• Ordene los bordes del gráfico con respecto a sus pesos.
• Comience a agregar bordes al MST desde el borde con el menor peso hasta el borde del mayor peso.
• Solo agregue bordes que no formen un ciclo, bordes que conectan solo componentes desconectados.

O como una explicación más simple,

Paso 1 – Eliminar todos los bucles y bordes paralelos

Paso 2 – Organice todos los bordes en orden ascendente de costo

Paso 3: agregue bordes con el menor peso

Pero, ¿cómo verifica si dos vértices están conectados o no? Ahí es donde entra en uso la aplicación real de Disjoint Sets.

El algoritmo de Kruskal explicado con un ejemplo.

Estoy seguro de que muy pocos de ustedes estarían trabajando para una compañía de redes de cable, así que hagamos que el problema del algoritmo de Kruskal sea más fácil de identificar.

En su viaje a Venecia, planea visitar todos los sitios importantes del patrimonio mundial, pero tiene poco tiempo. Para que su itinerario funcione, decide utilizar el algoritmo de Kruskal utilizando conjuntos disjuntos.

Aquí hay un mapa de Venecia.

Simplifiquemos el mapa convirtiéndolo en un gráfico como se muestra a continuación y nombrando ubicaciones importantes en el mapa con letras y distancia en metros (x 100).

Comprendamos cómo se usa el algoritmo de Kruskal en aplicaciones del mundo real usando el mapa anterior.

Paso 1- Eliminar todos los bucles y bordes paralelos

Entonces, para el mapa dado, tenemos un borde paralelo que corre entre Madonna dell’Orto (D) y la Basílica de San Marcos (J), que tiene una longitud de 2.4kms (2400mts). Eliminaremos la carretera paralela y conservaremos la longitud de 1.8 km (1800 m) para la representación.

Paso 2 – Organice todos los bordes en el gráfico en orden ascendente. El algoritmo de Kruskal considera a cada grupo como un árbol y aplica conjuntos disjuntos para verificar cuántos de los vértices son parte de otros árboles.

Paso 3: agregue bordes con el menor peso; comenzamos con los bordes con menor peso / costo. Por lo tanto, B, C se conecta primero considerando su costo de borde solo 1

I, J ha costado 1; Es el borde conectado a continuación.

Luego, conectamos los bordes con peso = 2.

Del mismo modo, conectamos el nodo K, L que tiene una arista con peso = 3.

Como se indica en la tabla anterior, todos los bordes están conectados en orden ascendente, asegurando que no se forme un bucle o ciclo entre 2 vértices.

Esto nos da el siguiente gráfico, que es el árbol de expansión mínimo para el problema dado.

Después de comprender cómo funciona el algoritmo de Kruskal, es importante comprender la diferencia entre MST y TSP.

Problema de árbol de expansión mínimo vs. vendedor ambulante

Un árbol de expansión mínimo lo ayuda a construir un árbol que conecta todos los nodos, o como en el caso anterior, todos los lugares / ciudades con un peso total mínimo. Mientras que un problema de vendedor ambulante (TSP) requiere que visite todos los lugares mientras regresa a su nodo inicial con un peso total mínimo.

Las siguientes son algunas de las otras aplicaciones de la vida real del algoritmo de Kruskal:

1. Cables de aterrizaje
2. Red de televisión
3. Operaciones de tour

Puede encontrar el código C ++ para el algoritmo de Kruskal: aquí

Mantendré mi respuesta corta. Una estructura de datos realmente buena que he usado en mi trabajo es un ‘Filtro Bloom’. Definitivamente, puede leer más sobre los filtros de floración en su página de wikipedia, pero esencialmente un filtro de floración es un mapa de bits que probablemente conoce la presencia o ausencia de datos. Debido a su uso de bits para predecir la presencia o ausencia de un elemento, es altamente eficiente en cuanto al espacio y no cuesta casi nada mantenerlo residente en la memoria.

Aplicación de la vida real

Te daré un caso de uso muy común. Cuando tratamos con grandes datos y utilizamos bases de datos NoSql (como HBase, DynamoDB, etc.), los datos pueden explotar en tal medida que, en muchas circunstancias, hacemos una copia de seguridad de un fragmento en un sistema de archivos distribuido (como HDFS o S3). Estos son escenarios realmente comunes debido a la escala de datos de producción que las empresas con cientos de millones de clientes / usuarios generan todos los días. Aquí es donde el filtro de floración actúa como una bendición.

Con un filtro Bloom, puede mover fácilmente los datos ‘probabilísticamente antiguos’ al almacenamiento distribuido y mantener un filtro Bloom en la memoria y, antes de realizar una búsqueda en el disco, le preguntamos si está presente en el disco o no. Debido a la propiedad de cero falsos negativos, un “no” de un filtro de floración es un “no” garantizado, pero un “sí” es esencialmente un “tal vez”. Por lo tanto, nos brinda una forma económica de optimizar la segregación de una determinada porción de datos en el almacenamiento y mantener los datos utilizados más recientemente en la memoria y preguntarle al BloomFilter sobre dónde se pueden ubicar los datos asociados con una clave, reduciendo así el número amortizado de búsquedas de disco que hacer con el tiempo, así como optimizar el almacenamiento de datos en sistemas de bases de datos en memoria.

Árboles especiales, listas especiales y estructuras de datos probabilísticos:

Lista de saltos:
Utilizado por el almacén de datos Redis para la implementación de conjuntos ordenados.
Utilizado en nessDB.

Filtro de floración:
Usado por Cassandra para verificar qué SSTables contiene principalmente la clave.
Hbase también lo usa para optimizar las lecturas.

Splay Tree:
Utilizado en cachés.

Árbol de sufijos:
Secuenciación genómica.

Árboles LSM:
Usado por Cassandra (SSTables), Mesa grande para almacenamiento.

Árbol de Merkle:
Usado por varios almacenes de datos eventualmente consistentes como Dynamo, Cassandra para el mecanismo anti-entropía.

Bien, permítanme agregar uno más a esta lista completa de estructuras de datos avanzadas y su aplicación de la vida real.
Estaba investigando un poco sobre el algoritmo de inteligencia artificial que usa el juego EA Fifa y encontré esta increíble estructura de datos llamada “R-Tree”.
Los árboles R se usan específicamente para métodos de acceso espacial, por ejemplo, para manejar eficientemente consultas espaciales, como la diferencia entre dos puntos, o si los puntos caen dentro de un área espacial de interés, etc.

Cito el siguiente ejemplo de wikipedia:
Un uso común en el mundo real para un árbol R podría ser almacenar objetos espaciales como ubicaciones de restaurantes o los polígonos de los que están hechos los mapas típicos: calles, edificios, contornos de lagos, costas, etc. y luego encontrar respuestas rápidamente a las consultas como “Buscar todos los museos a menos de 2 km de mi ubicación actual”, “recuperar todos los segmentos de la carretera a menos de 2 km de mi ubicación”

Y al profundizar un poco más en lo que estaba buscando, descubrí que EA usa R Trees para colocar a esos 10 jugadores en diferentes secciones y mantener sus movimientos y la densidad general del campo, por lo que nos da un sentido “distribuido”. La implementación típica en Java se puede encontrar aquí: JSI (Java Spatial Index) RTree Library

Quiero hablar sobre una increíble estructura de datos en memoria que aún no se discute en este hilo

JudyTree es la estructura de datos eficiente en memoria que es rápida y consume menos memoria

Judy tiene dos estrategias principales: usar un árbol de 256 arios, comprimido y diseñado para requerir una (como máximo dos) fallas de caché secundarias por búsquedas de nodos de árbol

Un relleno de línea de caché (CPU) es tiempo adicional requerido para leer de la RAM cuando no se encuentra una palabra en la caché.
En las computadoras actuales, el tiempo para el llenado de la línea de caché está en el rango de 50..2000 instrucciones de la máquina.
Por lo tanto, se debe evitar un relleno de línea de caché cuando menos de 50 instrucciones pueden hacer el mismo trabajo.

* Judy es generalmente más rápido que un método de hashing y formas populares de árbol binario equilibrado
* Judy es caché, consciente porque está diseñado para evitar rellenos de línea de caché siempre que sea posible
* Judy Tree es más eficiente en memoria que casi cualquier otra estructura competitiva

enlace útil:
UNA DESCRIPCIÓN DE 10 MINUTOS DE CÓMO FUNCIONA JUDY ARRAYS Y POR QUÉ SON TAN RÁPIDOS

• Cola:

• Procesos de cola : cualquier dispositivo no tiene recursos infinitos, por lo que se debe usar una cola para asignar recursos a los procesos que lo necesitan en un nivel de prioridad.

• SIG : en Sistemas de Información Geográfica, transporte y tecnología vehicular.
• Mapas : Google Maps, Bing, etc.
• Rutas entre puntos ( claves ) : como el algoritmo A * , etc.

• Diseño de bases de datos : crear su propia base de datos solo para almacenar los datos en función de algún valor clave
• Creación de un sistema de archivos : los sistemas operativos mantienen el sistema de archivos de un disco como un árbol.
• Zoología : mantenimiento de las estructuras de todo el reino animal y vegetal.
• Redes sociales : establecer relaciones entre usuarios en función de alguna clave .

• Comercio electrónico : al acceder a claves únicas. B-Trees árbol de búsqueda multidireccional equilibrado de orden N.
• Búsqueda : búsqueda rápida de un elemento determinado.

Mi favorito personal es HyperLogLog [1] y HyperLogLogPlusPlus relacionado. La clase general de estructuras de datos LogLog utiliza probabilidades y un esquema de codificación inteligente para estimar la cardinalidad de conjuntos enormes en memoria muy pequeña. El reclamo inicial de la fama es que puedes contar mil millones de elementos únicos en 1,5 kilobytes de espacio. Estas estructuras de datos son rápidas, fáciles de serializar y deserializar, y admiten operaciones de unión e intersección. Stream-Lib es una implementación de código abierto (Java) de HLL y otras estructuras de datos interesantes.

[1] – Página sobre Algo
[2] – HyperLogLog en la práctica: ingeniería algorítmica de un algoritmo de estimación de cardinalidad de última generación
[3] – stream-lib

Filtro Bloom: en la biblioteca WebKit (utilizada en la mayoría de los navegadores modernos) para encontrar símbolos CSS. Además, en Chromium para una búsqueda rápida de URL de la lista de navegación segura.

Buena fuente es la clase de CMU “Algoritmos en el mundo real”. Diapositivas, etc. disponibles en Algoritmos en el “Mundo Real”

Muchas ideas entran en TokuDB (con muchos ajustes):

• Árbol de repositorio almacenado en memoria intermedia / árbol de almacenamiento intermedio / COLA / etc.
• Árbol de mantenimiento de pedidos
• Matriz de memoria empaquetada (históricamente)
• Clasificación de memoria externa
• Árbol concurrente de AVL

B-tree es otro ejemplo de una estructura de datos ampliamente utilizada en sistemas informáticos de la vida real como bases de datos y sistemas de archivos. Más aquí:
Árbol B

Gráfico de De Bruijn: utilizado en el ensamblaje del genoma para lecturas muy cortas. Siempre me ha parecido bastante exótico.

Trie (árbol de prefijos):

• en diccionario de autocompletar en móviles, motores de búsqueda, etc.
• como algoritmos aproximados en la corrección ortográfica

búsquedas rápidas de datos (por ejemplo, ¿toleraría más de 5 minutos para que este sitio encuentre algo)? para cosas avanzadas, las aplicaciones se vuelven aún mayores como Facebook y todas las demás redes sociales son imposibles sin un conocimiento de gráficos.

Dos de las implementaciones principales de mapas y conjuntos en Java se basan en árboles rojo-negros, árboles, mapas de árboles.