Problema de mantenimiento de pedidos

En informática , el problema de mantenimiento del orden implica mantener un conjunto totalmente ordenado que admita las siguientes operaciones:

• insert(X, Y), que inserta X inmediatamente después de Y en el orden total;
• order(X, Y), que determina si X precede a Y en el orden total; y
• delete(X), que elimina X del conjunto.

Paul Dietz introdujo por primera vez una estructura de datos para resolver este problema en 1982. ^[1] Esta estructura de datos admite insert(X, Y)in (en notación Big O ) tiempo amortizado y en tiempo constante, pero no admite la eliminación. Athanasios Tsakalidis utilizó árboles BB[α] con los mismos límites de rendimiento que admiten la eliminación en y mejoraron el rendimiento de inserción y eliminación en tiempo amortizado con indirección. ^[2] Dietz y Daniel Sleator publicaron una mejora al tiempo constante en el peor de los casos en 1987. ^[3] Michael Bender, Richard Cole y Jack Zito publicaron alternativas significativamente simplificadas en 2002. ^[4] Bender, Fineman, Gilbert, Kopelowitz y Montes también publicaron una solución desamortizada en 2017. ^[5] ${\displaystyle O(\log n)}$order(X, Y) ${\displaystyle O(\log n)}$ ${\displaystyle O(1)}$

Las estructuras de datos eficientes para el mantenimiento de pedidos tienen aplicaciones en muchas áreas, incluidas la persistencia de estructuras de datos , ^[6] algoritmos de gráficos ^{[7] [8]} y estructuras de datos tolerantes a fallas. ^[9]

Etiquetado de listas

Un problema relacionado con el problema de mantenimiento del orden es el problema de etiquetado de listas en el que, en lugar de la order(X, Y)operación, la solución debe mantener una asignación de etiquetas de un universo de números enteros a los elementos del conjunto de modo que X preceda a Y en el orden total si y solo si a X se le asigna una etiqueta menor que Y. También debe admitir una operación que devuelva la etiqueta de cualquier nodo X. Nótese que se puede implementar simplemente comparando y de modo que cualquier solución al problema de etiquetado de listas dé inmediatamente una al problema de mantenimiento del orden. De hecho, la mayoría de las soluciones al problema de mantenimiento del orden son soluciones al problema de etiquetado de listas aumentadas con un nivel de indirección de la estructura de datos para mejorar el rendimiento. Veremos un ejemplo de esto a continuación. ${\displaystyle \{1,2,\ldots ,m\}}$label(X)order(X, Y)label(X)label(Y)

Para un problema de etiquetado de listas en conjuntos de tamaño hasta , el costo del etiquetado de listas depende de cuán grande sea una función de . El rango de parámetros relevante para el mantenimiento del orden es para , para el cual se conoce una solución de costo amortizado, ^[10] y para el cual se conoce una solución amortizada en tiempo constante ^[11]. ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle m=n^{1+\Theta (1)}}$ ${\displaystyle O(\log n)}$ ${\displaystyle 2^{\Omega (n)}}$

O(1) inserción amortizada por indirección

La indirección es una técnica utilizada en estructuras de datos en la que un problema se divide en varios niveles de una estructura de datos para mejorar la eficiencia. Normalmente, un problema de tamaño se divide en problemas de tamaño . Por ejemplo, esta técnica se utiliza en intentos y-fast . Esta estrategia también funciona para mejorar el rendimiento de inserción y eliminación de la estructura de datos descrita anteriormente con un tiempo amortizado constante. De hecho, esta estrategia funciona para cualquier solución del problema de etiquetado de listas con tiempo de inserción y eliminación amortizado. ${\displaystyle n}$ ${\displaystyle n/\log n}$ ${\displaystyle \log n}$ ${\displaystyle O(\log n)}$

Estructura de datos de mantenimiento de orden con indirección. Los elementos totales del orden se almacenan en sublistas contiguas de tamaño , cada una de las cuales tiene un representante en el árbol de chivos expiatorios . ${\displaystyle O(N/\log N)}$ ${\displaystyle O(\log N)}$

La nueva estructura de datos se reconstruye completamente cuando se hace demasiado grande o demasiado pequeña. Sea el número de elementos del orden total cuando se reconstruyó por última vez. La estructura de datos se reconstruye siempre que se viola el invariante mediante una inserción o eliminación. Dado que la reconstrucción se puede realizar en tiempo lineal, esto no afecta el rendimiento amortizado de las inserciones y eliminaciones. ${\displaystyle N}$ ${\displaystyle {\tfrac {N}{3}}\leq n\leq 2N}$

Durante la operación de reconstrucción, los elementos del orden total se dividen en sublistas contiguas, cada una de tamaño . El problema de etiquetado de listas se resuelve en el conjunto de nodos que representan cada una de las sublistas en su orden de lista original. Las etiquetas para este subproblema se toman como polinómicas, es decir , de modo que se puedan comparar en tiempo constante y actualizar en tiempo amortizado. ${\displaystyle N}$ ${\displaystyle O(N/\log N)}$ ${\displaystyle \Omega (\log N)}$ ${\displaystyle m=N^{2}}$ ${\displaystyle O(\log N)}$

Para cada sublista se construye una lista doblemente enlazada de sus elementos, almacenando con cada elemento un puntero a su representante en el árbol, así como una etiqueta entera local. Las etiquetas enteras locales también se toman de un rango , de modo que se puedan comparar en tiempo constante, pero como cada problema local involucra solo elementos, el rango de etiquetas es exponencial en el número de elementos que se etiquetan. Por lo tanto, se pueden actualizar en tiempo amortizado. ${\displaystyle m=N^{2}}$ ${\displaystyle \Theta (\log N)}$ ${\displaystyle m}$ ${\displaystyle O(1)}$

Consulte el problema de etiquetado de listas para obtener detalles de ambas soluciones.

Orden

Dados los nodos de la sublista X e Y, order(X, Y)se puede responder comprobando primero si los dos nodos están en la misma sublista. Si es así, su orden se puede determinar comparando sus etiquetas locales. De lo contrario, se comparan las etiquetas de sus representantes en el primer problema de etiquetado de listas. Estas comparaciones toman un tiempo constante.

Insertar

Dado un nuevo nodo de sublista para X y un puntero al nodo de sublista Y, insert(X, Y)inserta X inmediatamente después de Y en la sublista de Y, si hay espacio para X en la lista, es decir, si la longitud de la lista no es mayor que después de la inserción. Su etiqueta local la proporciona el algoritmo de etiquetado de listas locales para etiquetas exponenciales. Este caso requiere tiempo amortizado. ${\displaystyle 2\log N}$ ${\displaystyle O(1)}$

Si la lista local se desborda, se divide de manera uniforme en dos listas de tamaño , y a los elementos de cada lista se les asignan nuevas etiquetas de sus rangos (independientes). Esto crea una nueva sublista, que se inserta en la lista de sublistas, y al nuevo nodo de la sublista se le asigna una etiqueta en la lista de sublistas mediante el algoritmo de etiquetado de listas. Finalmente, se inserta X en la lista correspondiente. ${\displaystyle \log N}$

Esta secuencia de operaciones lleva tiempo, pero se han producido inserciones desde que se creó la lista o se dividió por última vez. Por lo tanto, el tiempo amortizado por inserción es . ${\displaystyle O(\log N)}$ ${\displaystyle \Omega (\log N)}$ ${\displaystyle O(1)}$

Borrar

Dado un nodo de sublista X que se va a eliminar, delete(X)simplemente elimina X de su sublista en tiempo constante. Si esto deja la sublista vacía, entonces necesitamos eliminar el representante de la lista de sublistas. Dado que al menos se eliminaron elementos de la sublista desde que se creó por primera vez, podemos permitirnos dedicar el tiempo; el costo amortizado de una eliminación es . ${\displaystyle \Omega (\log N)}$ ${\displaystyle O(\log N)}$ ${\displaystyle O(1)}$

Referencias

1. Dietz, Paul F. (1982), "Mantener el orden en una lista enlazada", Actas del 14º Simposio Anual de la ACM sobre Teoría de la Computación (STOC '82) , Nueva York, NY, EE. UU.: ACM, págs. 122-127, doi : 10.1145/800070.802184 , ISBN 978-0897910705.
2. Tsakalidis, Athanasios K. (1984), "Mantener el orden en una lista enlazada generalizada", Acta Informatica , 21 (1): 101–112, doi :10.1007/BF00289142, MR  0747173.
3. Dietz, P.; Sleator, D. (1987), "Dos algoritmos para mantener el orden en una lista", Actas del 19.º Simposio Anual de la ACM sobre Teoría de la Computación (STOC '87) , Nueva York, NY, EE. UU.: ACM, págs. 365–372, doi : 10.1145/28395.28434 , hdl : 1802/5693 , ISBN 978-0897912211. Versión completa, Tech. Rep. CMU-CS-88-113, Carnegie Mellon University, 1988.
4. Bender, Michael A. ; Cole, Richard ; Demaine, Erik D. ; Farach-Colton, Martin ; Zito, Jack (2002), "Two simplifyd algorithms for keeping order in a list", en Möhring, Rolf H.; Raman, Rajeev (eds.), Algorithms – ESA 2002, 10th Annual European Symposium, Roma, Italia, 17–21 de septiembre de 2002, Actas , Lecture Notes in Computer Science, vol. 2461, Springer, págs. 152–164, doi :10.1007/3-540-45749-6_17
5. Bender, Michael A. ; Fineman, Jeremy T.; Gilbert, Seth; Kopelowitz, Tsvi; Montes, Pablo (2017), "Mantenimiento de archivos: en caso de duda, ¡cambie el diseño!", en Klein, Philip N. (ed.), Actas del vigésimo octavo simposio anual ACM-SIAM sobre algoritmos discretos, SODA 2017, Barcelona, ​​España, Hotel Porta Fira, 16-19 de enero , Society for Industrial and Applied Mathematics, pp. 1503-1522, doi : 10.1137/1.9781611974782.98
6. Driscoll, James R.; Sarnak, Neil; Sleator, Daniel D .; Tarjan, Robert E. (1989), "Hacer que las estructuras de datos sean persistentes", Journal of Computer and System Sciences , 38 (1): 86–124, doi : 10.1016/0022-0000(89)90034-2 , MR  0990051.
7. Eppstein, David ; Galil, Zvi ; Italiano, Giuseppe F. ; Nissenzweig, Amnon (1997), "Esparcimiento: una técnica para acelerar los algoritmos de gráficos dinámicos", Journal of the ACM , 44 (5): 669–696, doi : 10.1145/265910.265914 , MR  1492341.
8. Katriel, Irit; Bodlaender, Hans L. (2006), "Ordenamiento topológico en línea", ACM Transactions on Algorithms , 2 (3): 364–379, CiteSeerX 10.1.1.78.7933 , doi :10.1145/1159892.1159896, MR  2253786 .
9. Aumann, Yonatan; Bender, Michael A. (1996), "Estructuras de datos tolerantes a fallos", Actas del 37.º Simposio anual sobre fundamentos de la informática (FOCS 1996) , págs. 580-589, doi :10.1109/SFCS.1996.548517, ISBN 978-0-8186-7594-2.
10. Itai, Alon; Konheim, Alan G.; Rodeh, Michael (1981), "Una implementación de colas de prioridad mediante tablas dispersas", ICALP , págs. 417–431
11. Bulánek, Jan; Koucký, Michal; Saks, Michael E. (2015), "Límites inferiores estrictos para el problema de etiquetado en línea", SIAM Journal on Computing , vol. 44, págs. 1765--1797.

Enlaces externos

• Dos algoritmos simplificados para mantener el orden en una lista. - Este artículo ( Michael A. Bender , Richard Cole, Erik D. Demaine , Martin Farach-Colton y Jack Zito, 2002) presenta una estructura de datos de etiquetado de listas con rendimiento amortizado que no almacena explícitamente un árbol. El análisis dado es más simple que el dado por (Dietz y Sleator, 1987) para una estructura de datos similar.