Buenos días, así que aquí está mi problema. Y lo siento de antemano si mi inglés no es perfecto. De todos modos, tengo una gran cantidad de relación entre los números formados así:
$relation1 = [1, 2];
$relation2 = [2, 3];
$relation3 = [4, 5];
$relation4 = [6, 7];
$relation5 = [7, 2];
Cada matriz representa una relación entre los 2 números. Lo que necesito hacer es fusionar las relaciones para obtener un resultado como:
$result1 = [1, 2, 3, 6, 7];
$result1 = [4, 5];
Ya desarrollé un algoritmo en PHP que hace exactamente eso, el problema es que para un total de más de 50000 relaciones, el programa tarda mucho tiempo en ejecutarse. Cuando termine de crear relaciones directas, que no requieren mucho tiempo:
$temporary_result1 = [1, 2, 3];
$temporary_result2 = [4, 5];
$temporary_result3 = [6, 7, 2];
Luego necesito fusionar los grupos 1 y 3, pero con alrededor de 20 000 grupos creados previamente, el proceso lleva mucho tiempo, porque necesito iterar 20 000 * 20 000 veces (400 000 000) que ya lleva alrededor de 30 minutos. Como se espera que el número de relaciones crezca en el tiempo extra, me preocupa que el tiempo de ejecución crezca exponencialmente ya que necesito ejecutar el programa todos los días.
Me preguntaba si existía un algoritmo existente que haga esto, a la vez que sea más eficiente, en cualquier lenguaje de programación que pueda intentar y recodificar en PHP.
2 respuestas
Puede ver estas relaciones como paquetes de Composer. Cada paquete tiene su propia dependencia.
Como por ejemplo,
$relation1 = [1, 2];
$relation2 = [2, 3];
En el ejemplo anterior, puede decir que el paquete
1
depende del paquete2
y el paquete2
depende del paquete3
.Del mismo modo, tenemos que encontrar todos los componentes conectados. La relación entre 2 paquetes no necesariamente tiene que ser reflexiva, lo que significa que el paquete
A
depende del paqueteB
no necesariamente significa que el paqueteB
depende del paquete { {X3}}.Pero para el alcance de este problema, podemos hacer que la relación sea reflexiva para obtener los componentes conectados a través de {{ X0}}. Si lo desea, puede adaptarse a una idea no reflexiva utilizando
union find by path compression
para fusionar valores con padres singulares, pero en mi respuesta, me quedaría con DFS.
Su entrada:
$relation1 = [1, 2];
$relation2 = [2, 3];
$relation3 = [4, 5];
$relation4 = [6, 7];
$relation5 = [7, 2];
Para la entrada anterior, la lista de adyacencia se vería así:
1 => 2
2 => 1,3,7
3 => 2
4 => 5
5 => 4
6 => 7
7 => 6,2
Fragmento:
function getConnectedComponents($relations,$total_nodes){
$result = [];
$nodes = [];
$visited = [];
for($i=1;$i<=$total_nodes;++$i){
$nodes[$i] = [];
$visited[$i] = false;
}
foreach($relations as $relation){
$nodes[$relation[0]][] = $relation[1];
$nodes[$relation[1]][] = $relation[0];
}
for($i=1;$i<=$total_nodes;++$i){
if(!$visited[$i]){
$temp = [];
dfs($nodes,$i,$visited,$temp);
$result[] = $temp;
}
}
return $result;
}
function dfs($nodes,$node,&$visited,&$temp){
if($visited[$node]) return;
$visited[$node] = true;
$temp[] = $node;
foreach($nodes[$node] as $child_node){
dfs($nodes,$child_node,$visited,$temp);
}
}
Demostración: https://3v4l.org/JWAF6
En el algoritmo anterior, construimos la lista de adyacencia y hacemos una búsqueda profunda en primer lugar en cada nodo. Marcamos los nodos como visitados en el camino para asegurarnos de que no estamos visitando algo que ya procesamos.
Puede ver este problema como un problema de gráficos generales.
Sus relaciones son aristas y hay E
de ellas.
Sus enteros son vértices, hay V
de ellos.
Ahora necesita encontrar los componentes del gráfico, este es un problema bien conocido y hay muchas soluciones para ello.
Se describe una solución aquí, comienza de forma aleatoria nodo y haga un DFS
hasta que encuentre todos los nodos en su componente. Que pasar a otro nodo no visitado hasta encontrar todos los nodos en el gráfico.
Presenta un código en muchos idiomas, pero no PHP
, aquí hay una implementación php de DFS que puedes usar.
La complejidad temporal de esta solución es O(E + V)
si se implementa correctamente, por lo que resolverá el problema del tiempo de ejecución.
La mejor de las suertes
Nuevas preguntas
php
PHP es un lenguaje de secuencias de comandos interpretado, dinámico, orientado a objetos y ampliamente utilizado, diseñado principalmente para el desarrollo web del lado del servidor. Se utiliza para preguntas sobre el lenguaje PHP.