El título completo del artículo debería haber sido la clasificación "topológica" sostenible de un gráfico con ciclos en
O(|V| + |e| log |e|) en el tiempo y
O(|V|) en la memoria sin recurrencia ", pero me dijeron ¿Qué es exagerar?
Descargo de responsabilidad: soy un programador, no un matemático, por lo que el lenguaje inexacto es posible en lugares, por lo que puedes y debes patear.
Esencia de la tarea.
Analizaré la redacción del problema, cuya solución quiero compartir, en partes.
La ordenación topológica es el orden de los vértices de un gráfico acíclico dirigido en el que cada uno de los vértices del que sale el borde llega antes que el vértice en el que entra este borde. Aquí hay dos matices importantes: un gráfico puede tener
más de uno de esos ordenamientos y solo es aplicable a los gráficos
acíclicos . A los matemáticos no les importa, pero los programadores a veces quieren determinismo y un poco más que "lo siento, tienes un ciclo aquí, no tendrás ninguna clasificación".
Por lo tanto, agregamos el requisito de
estabilidad : un par de vértices, cuyo orden no está dado por los bordes del gráfico, debe determinarse por el orden en que estos vértices llegaron a la entrada del algoritmo. Como resultado, las ordenaciones repetidas no cambiarán el orden de los vértices.
Con la falta de
recursividad, todo es simple, la computadora es significativamente más débil que la máquina de Turing y la memoria (y especialmente la pila) se ha limitado. Por lo tanto, en la programación aplicada, generalmente los algoritmos iterativos son preferibles a los recursivos.
Y finalmente, definiré lo que llamo clasificación "topológica" si hay
ciclos en el gráfico. Este es el orden de los vértices, que coincide con la verdadera clasificación topológica, si cada uno de los ciclos se reemplaza por un vértice, y los vértices del ciclo en sí, de acuerdo con el requisito de estabilidad, se ubican entre sí en el orden original.
Y ahora
con toda esta basura intentaremos despegar. Lo haré todo dentro del marco de tiempo y restricciones de memoria indicadas al comienzo de la publicación.
Busca una solución
Si observa los algoritmos existentes para la clasificación topológica (
algoritmo de Kahn ,
búsqueda profunda ), resulta que todos ellos, si hay un ciclo, dicen "No puedo" y dejan de funcionar.
Por lo tanto, vamos por otro lado, con algoritmos que pueden hacer algo inteligible con los ciclos. Por ejemplo,
encuéntralos . Entre los
algoritmos enumerados en Wikipedia
para encontrar ciclos en gráficos , se llamó la atención sobre
el algoritmo Taryan . Contiene una observación interesante de que, como subproducto, el algoritmo produce la clasificación topológica
inversa del gráfico:
Si bien no hay nada especial en el orden de los nodos dentro de cada componente fuertemente conectado, una propiedad útil del algoritmo es que no se identificará ningún componente fuertemente conectado antes que ninguno de sus sucesores. Por lo tanto, el orden en el que se identifican los componentes fuertemente conectados constituye un tipo topológico inverso del DAG formado por los componentes fuertemente conectados .
Es cierto que el algoritmo es recursivo y no está claro qué tiene con la estabilidad, pero esto es claramente un movimiento en la dirección correcta. Una lectura más cercana de Wikipedia revela una referencia al artículo
Un algoritmo de espacio eficiente para encontrar componentes fuertemente conectados , escrito por el compañero David Pearce, en el que no solo existe un algoritmo imperativo, sino que también ha reducido los requisitos de memoria en comparación con el clásico El algoritmo de Tarjan. La ventaja es la
implementación del algoritmo en Java . Debe tomar!
Algoritmo PEA_FIND_SCC3 (V, E) del artículo de Pierce Entonces, tenemos una lista de vértices en la entrada y (gracias a Pierce) un cierto índice del componente de conectividad fuerte al que pertenece este vértice en la salida. El siguiente paso es ordenar de manera estable los vértices de acuerdo con el número de serie de su componente. Hay un algoritmo para tal tarea, se llama
ordenación de conteo , que realiza esto en tiempo
O(n) .
En el proceso de reunir el algoritmo en un montón, resultó que el hecho de que sea natural darle la clasificación topológica
opuesta realmente está saliendo de Taryan; luego, las ramas vecinas del gráfico (que no tienen una relación de orden entre ellas) numerarán hacia atrás, luego las piezas del gráfico no teniendo alguna conexión entre ellos, resulta estar en el orden inverso ...
La respuesta
Entonces la solución final:
- Numeramos los vértices de la lista original.
O(|V|) - Ordenamos los bordes de cada vértice de acuerdo con el número del vértice al que va el borde.
O(|e| log |e|) - Usando el algoritmo de Pierce, encontramos y numeramos los componentes de una conexión fuerte.
O(|V|) - Usando la clasificación contando, clasificamos los vértices en función de los números de los componentes fuertemente conectados que recibieron.
O(|V|)
Código GitHub, Java, dominio público . Cabe señalar que para garantizar la estabilidad de la clasificación, el algoritmo de Pierce se modifica ligeramente y evita los vértices en el orden inverso.
¿Pero por qué?
Y ahora el trasfondo, por qué se necesitaba todo esto. Al cargar / descargar bibliotecas dinámicas (.so), glibc necesita decidir en qué orden inicializar las variables estáticas. Las variables dependen unas de otras, dependen de diferentes funciones, etc. En general, todo esto forma el gráfico mismo en el que hay ciclos y que deben ser ordenados.
Érase una vez, un código bastante subóptimo que realizaba la tarea para
O(n^2) estaba involucrado en esta tarea. Y en general, esto realmente no molestó a nadie, hasta que en 2012 se
descubrió que el código no funcionaba correctamente y en algunos casos estaba equivocado.
Los hombres rudos de RedHat pensaron, pensaron y arruinaron algunos ciclos más desde arriba. Se repararon los casos problemáticos, pero el algoritmo comenzó a funcionar para
O(n^3) , y esto ya se hizo evidente y en algunas aplicaciones comenzó a tomar varias decenas de segundos, lo que fue un
error en 2013. Además, el autor del error descubrió casos en los que el algoritmo con
O(n^3) también O(n^3) equivocado . Sugirió usar el algoritmo Taryan, aunque el parche con correcciones nunca se ha diseñado.
Y pasó el tiempo, glibc se desaceleró sin piedad y en 2015 hubo
otro intento de reparar el algoritmo . Desafortunadamente, sin éxito, el algoritmo se eligió
O(n^2) , además de confundir las ramas del gráfico, entre las cuales el orden no está definido.
Hoy es el año 2019, glibc todavía se está desacelerando. A juzgar por el tiempo que me llevó solucionar el problema, las posibilidades de que lo solucione son significativamente inferiores al 100%. Esto se agrava aún más por el hecho de que las cosas están sucediendo en C, sin compatibilidad con IDE, en el código de estilo de codificación GNU, corredor de prueba loco ("si desea ejecutar la prueba nuevamente, simplemente elimine el archivo .out correspondiente"). Y para que glibc eche un vistazo a su parche, debe seguir el procedimiento de
asignación de derechos de autor , emitir el parche correctamente y el diablo sabe qué más. Por lo tanto, para eliminar al menos el problema de inventar un algoritmo que resuelva el problema, se escribió esta publicación.