[l-desarrollo] Perl "Out of Memory"

[Jesus A. Dominguez S.]

Hola a todos, 

estoy teniendo problemas con un script de perl. Se cual es el problema pero no se como solucionarlo...

Tengo una tabla con 6millones y medio de filas de esta forma :

      autor -> co_autor

Necesito hacer un algoritmo que me encuentre la relación entre un autor a otro (el camino entre autores), es decir, teniendo algo así:

autor | coautor

   1         2

   2         5

   5         9

si quiero el camino entre el autor 1 y el 9, me devolvería: 1-2-5-9

Hasta ahi todo bien, lo estoy haciedo de la siguiente forma:

Con la libreria _Graph_ creo un grafo de la siguiente forma:

--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

        my $g = Graph::Undirected->new;

my $conexion = DBI->connect("dbi:mysql:database=$database; host=$host", $user, $password) or die "No Se pudo conectar con la Base de Datos: $!\n";

my $query_handle = $conexion->prepare("SET NAMES 'utf8'"); $query_handle->execute();

my $query = "SELECT id_autor, id_coautor FROM tb_relationships";

$query_handle = $conexion->prepare($query);

$query_handle->execute();

while(my $row = $query_handle->fetchrow_hashref()) {

$g->add_edges($row->{'id_autor'},$row->{'id_coautor'});

}

$query_handle->finish;

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Ya con el grafo cargado ejecuto (ya aquí tengo el 70% de la memoria full):

my $apsp = $g->APSP_Floyd_Warshall();

en $apsp debería cargar un grafo de caminos entre autores, con pocos datos funciona bien pero con 6millones y pico explota, porque obviamente no tengo tanta memoria como para soportar ambos grafos cargados... Mi idea es ya teniendo los caminos, guardarlos en otra tabla para no tener que cargar los grafos de nuevo...

So, mi pregunta es... hay otra forma de hacerlo? que no cargue los grafos en memoria o algo asi? u otra forma de hacerlo?

Gracias por su ayuda...

Saludos

--

Jesús A. Domínguez S.

[William Yanez]

Saludos Jesús,

El 1er *problema* que veo es que estas usando el algoritmo de Floyd Warshall, lo cual conceptualmente está mal ya que quieres obtener la ruta más corta de un vértice a otro, Floyd te devuelve la ruta más corta de *todos* los Vertices al resto (APSP en el nombre del método significa "All Pair Shortest Path" ) , además Floyd Warshall es de complejidad cúbica (O|V³|)  lo cual debe ser evitado siempre que sea posible... (para representar el grafo en memoria usa una matriz de adyacencias lo cual empeora tu problema)...

Por lo tanto para tu caso usa el voráz Algoritmo de Dijkstra (SSPP_Dijkstra en Graph, SSPP "Single Source Shortest Path") que te devuelve los caminos mas cortos al resto de los vértices desde un origen dado y es de complejidad logarítmica (lo cual es bueno)  cuando se implementa con un Heap (montículo) (O|E+Vlog(V)|). 

Como estás en una de pruebas, puedes probar con Bio::Cordinate::Graph que también tiene una implementación de Dijkstra.

Espero haberte ayudado,

--
William R. Yánez R.
Email: wya...@gmail.com
twitter/identi.ca: @wryanez

[William Yanez]

Saludos a todos, 

Otra cosa Jesús, y tal vez la más obvia que la omití en el email anterior, es que como tu Grafo es No-Ponderado (las aristas  no tienen peso) antes de aplicar el algoritmo para buscar la distancia más corta entre los nodos a y b debes comprobar si hay una arista que una a y b, si es así resuelto tu problema, es decir cuando estas procesando tu entrada vas chequeando esto y si se cumple no es necesario seguir procesando el resto de los registros... Si esto no se cumple, aplicas tu algoritmo de distancia más corta (Dijkstra como te sugerí en el email anterior) .

Nota: Si el Grafo fuera Ponderado si hay que aplicar el algoritmo de todas todas, ya que no es cierto para todos los casos que Dist(i,j)< Dist(i,k)+Dist(k,j). 

[Jesus A. Dominguez S.]

Gracias! Pruebo y cuento que tal...

_______________________________________________
l-desarrollo mailing list
l-desa...@velug.org.ve
http://listas.velug.org.ve/mailman/listinfo/l-desarrollo

[Jesus A. Dominguez S.]

Gracias, no habia visto esta respuesta, interesante propuesta.... Pruebo y cuento que tal...

Saludos

2012/4/11 Ernesto Hernández-Novich <emhn...@gmail.com>

On Sun, 2012-02-12 at 19:50 +0100, Jesus A. Dominguez S. wrote:
[...]

> Con la libreria _Graph_ creo un grafo de la siguiente forma:

[...]

> So, mi pregunta es... hay otra forma de hacerlo? que no cargue los
> grafos en memoria o algo asi? u otra forma de hacerlo?
>

Te han dado otras alternativas usando Perl que probablemente funcionen.

Yo quiero aprovechar de presentar una solución que en mi opinión es
notablemente más atractiva porque se hace dentro de la base de datos y
probablemente ejecute muchísimo más rápido porque no hay que transferir
datos hacia la aplicación y porque puedes aprovechar índices.

Claro que requiere usar PostgreSQL que, a la fecha, es la única base de
datos que implanta SQL recursivo (Common Table Expressions) de la manera
más flexible posible, y para *este* problema en particular ofrece un
tipo de datos muy ameno.

El problema planteado se reduce a encontrar caminos, detectando ciclos,
en base a una tabla que hace referencia a sí misma. Esto requiere una
cantidad a priori desconocida de SELECT encadenados, y por eso la
solución de Jesús es natural: hacer un SELECT para convertirlo en grafo
y luego estudiar el grafo con algoritmos de grafos. Esto hace que saques
los datos de su ambiente natural, los transformes en otra representación
y apliques un algoritmo con sus propias condiciones de costo [1]

Sin embargo PostgreSQL permite hacer consultas recursivas basadas en un
algoritmo de punto fijo (algebráicos, ninguna relación con Falcón). Los
interesados pueden remitirse a la documentación pero el resumen es el
mismo que para cualquier cosa recursiva: hay un caso base, y se hace
UNION (o UNION ALL) de los valores inducidos, hasta que no se pueda
agregar nada.

Entonces, para abstraer el problema y aclarar la solución, supongamos
que se tiene una tabla

create table graph ( src integer, dst integer )

con cada fila modelando el hecho que existe una arista dirigida desde
'src' hacia 'dst'. Agreguen sus claves primarias si les interesa que NO
sea un multigrafo y agreguen columnas adicionales para modelar lo que
sea que le asocien a las aristas.

En tu problema, por la naturaleza de los datos representados, sería
absurdo que hubiera ciclos en el grafo. No obstante, yo si voy a
contemplar la posibilidad de que haya ciclos en los datos, así que
comencé con esta información:

emhn=> select * from graph;
 src | dst
-----+-----
  1 |   2
  1 |   3
  2 |   4
  4 |   5
  3 |   4
(5 rows)

Y luego, simplemente escribo la siguiente instrucción de SQL recursivo
para implantar DFS iterativo

with recursive related(src,dst,steps,path,cycle) as (
   select g.src, g.dst, 1, ARRAY[g.src], false
     from graph g
 union all
   select g.src, g.dst, r.steps + 1, path || g.src, g.src = ANY(path)
     from graph g, related r
    where g.src = r.dst and not cycle
)
select path || dst as camino from related;

con el resultado

 camino
-----------
 {1,2}
 {1,3}
 {2,4}
 {4,5}
 {3,4}
 {1,2,4}
 {1,3,4}
 {2,4,5}
 {3,4,5}
 {1,2,4,5}
 {1,3,4,5}
(11 rows)

que espero sea lo que estabas necesitando, caso contrario soy un idiota
que no comprendió la especificación.

Esto funciona así:

- 'related' es una tabla "virtual" construida recursivamente, con las
 columnas 'src', 'dst', 'steps', 'path' y 'cicle' cuyos tipos son
 *inferidos* por el manejador -- porque PostgreSQL tiene un sistema
 de tipos completos, como debe tener un RDBMS completo.

- La tabla 'related' se construye según un algoritmo de punto fijo
 que tiene un caso base y el caso inductivo:

 * El caso base es obvio -- incorporar todas las filas de origen
   a destino de la tabla real 'graph', con profundidad 1 (un paso,
   doh!) y con un camino que, por ahora, solamente tiene al nodo
   origen. Nótese que para el camino se usa el tipo de datos
   ARRAY de PostgreSQL.Además, el caso base indica que no hay ciclos
   por simplicidad.

 * El caso inductivo hace un JOIN entre la tabla real 'graph' y la
   *última* "versión" de la tabla virtual 'related'. El JOIN hace
   lo obvio, pues agrega un nuevo posible paso a la tabla virtual
   siempre y cuando no se agregue un ciclo (miren el WHERE) y
   en caso de ser agregado el nuevo paso, se aumenta el arreglo
   que contiene el camino, con el paso más reciente.

 * En virtud del UNION ALL en cada paso inductivo se combinan la
   versión anterior de 'related' con las nuevas filas generadas.
   Si se encontró un punto fijo, i.e. f(x) = f(x-1), entonces el
   algoritmo se detiene -- para los preocupados por la correctitud
   del algoritmo, haber verificado que no hay ciclos garantiza que
   hay un punto fijo (demostración se deja como ejercicio para el
   lector) y si yo no hubiera incorporado una invariante garante,
   PostgreSQL tiene control de recursión para darse cuenta e
   interrumpir la evaluación. Para *otros* problemas, que no este,
   se puede usar UNION en lugar de UNION ALL para además eliminar
   duplicados.


- Lo cierto es que al terminar las iteraciones, esta consulta
 calculó todos los caminos posibles haciendo la cantidad mínima
 necesaria de JOINs. Sólo me resta seleccionar la columna de
 mi interés, a la cual debo agregar "el último paso" de cada
 camino para que tenga sentido. Así, DFS iterativo en SQL puro.

Si, PostgreSQL es así de poderoso desde 8.4, bienvenidos a 2009.

No, no se puede con MySQL. Si algún día le ponen CTE (cosa difícil
porque carecen de la infraestructura necesaria en todos los niveles) no
tienen tipo arreglo con la semántica necesaria.

Se puede hacer algo similar con Oracle [2] con una sintaxis un poco más
odiosa y que no exhibe el comportamiento algorítmico de manera clara. Se
puede hacer parcialmente [3] en SQL-Server (la última vez que me lo
preguntaron, sólo se puede hacer UNION ALL y es *implícito* así que
eliminació).

Cada día encuentro más difícil comprender por qué la gente sigue usando
MySQL y su cara de poker ante las explicaciones cada vez luce más como
cara de poker del que perdió su all in con doble par.

Tarea para los interesados -- usar el tipo ARRAY en DBIx::Class para
convertirlo en un arreglo de Perl implícitamente like a boss.

[1] Creo que te lo apuntaron, pero tu quieres usar Floyd-Warshall
   para hacer algo que puedes lograr con DFS iterado. FW requiere
   mucha memoria y no hay nada que puedas hacer al respecto -- DFS
   iterado requiere menos memoria por iteración y al final del día
   tienes el mismo resultado.

[2] Pero Oracle no tiene tipo arreglo, así que la simplicidad de la
   consulta en Pg se destruye al tener que simular arreglos usando
   concatenación de cadenas para simularlo. Eso hace que la misma
   consulta sea más lenta en Oracle porque la concatenación de
   ARRAY en Pg es O(1) y la concatenación de cadenas en Pg es O(n)
   siendo n la longitud de la cadena prefijo. Saquen sus cuentas.

[3] Hará dos meses que un fanático de SQL-Server me preguntó si Pg tenía
   CTE y resultó evidente (para su desgracia) que SQL-Server sólo puede
   hacer UNION ALL y de manera implícita, así que cualquier
   eliminación de duplicados *tiene* que hacerla el programador
   incorporando las cláusulas necesarias en el WHERE del CTE. Eso sin
   contar que algunos problemas simplemente no se pueden representar.
   Capaz ya lo tienen, bien por ellos.

--
Ernesto Hernández-Novich - @iamemhn - Unix: Live free or die!
Geek by nature, Linux by choice, Debian of course.
If you can't aptitude it, it isn't useful or doesn't exist.
GPG Key Fingerprint = 438C 49A2 A8C7 E7D7 1500 C507 96D6 A3D6 2F4C 85E3

_______________________________________________
l-desarrollo mailing list
l-desa...@velug.org.ve
http://listas.velug.org.ve/mailman/listinfo/l-desarrollo