[Programación] Re: [Programación] Un problema de algoritmos II

[Alejandro Gomez Fernandez]

Lo tuyo es un problema de memoria? Proba con algo como esto:

La idea esta basada en la teoría de bases de datos relacionales y el
trabajo de normalización correspondiente, en este caso bastaría con una
3ra forma normal (por las ventajas que esto tiene):
-> Los datos del autor aparecen en una única ubicación => facilidad de
mantenimiento
-> Si eliminás algún tema de la lista no corres el riesgo de perder
datos de un autor
-> Podes tener datos de autores que no hayan escrito sobre alguno de
estos temas (previendo crecimiento de tu base de datos)
-> No tenes datos repetidos de autor. Lo único que se repite en la
estructura es sólo la dirección de la celda en la que se encuentran los
mismos => Aca es donde tenés el ahorro real de memoria. Fijate en esto:
por cada autor, unos 20/30 caracteres por cadena se repetiría en cada
tema sobre el que haya escrito frente a una cadena de 20/30 caracteres
en la lista de autores y tantos punteros a la celda (direcciones de  ...
2 a 4 bytes?) por cada referencia ... Ojo, estos datos son solo una
idea. Depende de la arquitectura y algunas otras cosas mas...)
Hay mas ventajas pero creo que con esto basta. 


Estrategia:

1) Hace una lista ordenada solo de autores (y depurala)
2) Hace una lista encadenada de temas (tambien depurada)
3) Depura la lista actual de autores en cada tema (para que no te
aparezcan repetidos -> tambien la tenes que depurar a mano. Ej: 
Jose de San Martin; San Martin; J. San Martin; San Martin, Jose y demás
variantes posibles ...)
4) Mientras recorrés la lista actual, armá una lista nueva de temas,
donde lo que guardás en la lista sea sólo la dirección (enlace a) de la
celda donde se encuentra en la lista de autores el autor mencionado. 
De esta forma te queda una lista de listas (una "principal") por temas
con listas transversales de autores, donde los autores no aparecen
nunca, sino sólo las referencias a la ubicacion donde se encuentran los
datos del autor, en una lista sélo de autores con múltiples referencias
"entrantes" para cada celda (tantas como temas haya escrito). Si querés
recorrer al revés, a partir de autores, la referencia va a tener que ser
doble, es decir, listas doblemente encadenadas ...

Espero haber sido claro con la idea. Si no es así, nos encontramos un
día de estos y lo vemos un poco mas en profundidad (siempre y cuando te
interese). 

Un abrazo, 



Alejandro.


On Mon, 2004-05-24 at 19:44, Horacio Castellini wrote:
> Holas.... queridos programadores....
> 
> Tengo un problema que seguramente el algoritmo existe, si alguien conoce como 
> se llama o me dá una punta para resolverlo se lo agradesco...  Porque estoy 
> confndido y no lo puedo obtimizar respecto de la memoria...
> 
> A ver... tengo dos listas enlazadas llamadas F[] y S[] donde la primera 
> guarda el nombre de personas y la segunda temas de conversación, como cadenas 
> de caracteres, el nombre de personas y temas con un 95,56% de probabilidad 
> están repetidos en cada lista. Ahora bien lo que intento hacer (asumiendo 
> capasidad de asignación dinámica, por lo tanto no me preocupo en definir 
> dimensión, etc...)
> 
> la dimensión de F y S es N, existen K1 temas distintos y K2 autores 
> distintos,  el arreglo de cadenas G está compuesto de K2+1 columnas y K1 
> filas donde en la primera columna se guarda el tema y en las restantes el 
> autor, inicialmente todos los elementos de G son el puntero (char*)NULL. Si 
> el autor ya fue grabado no puede volver a grabarlo sobre el mismo tema. 
> Entonces se me ocurrió... algo como esto...
> 
> llamar_a Clonar(S,Q) // duplica la lista
> llamar_a Clonar(F,T)
> // elimina lineas repetidas y las ordena, llena los sobrantes con (char*)NULL
> llamar_a Ordenar_Unificar(Q)
> llamar_a Ordenar_Unificar(T)
> k<-0
> mientras Q[k]<>NULL hacer
>      para i<-0 hasta N  hacer
>        si Q[k]=S[i] entonces
>            l<-0
>            mientras T[l]<>NULL hacer
>               si T[l]=F[i] y g[k,l]<>F[i] entonces
> 	      g[k,0]<-S[i]
>                   g[k,l]<-F[i]
>                finsi
>                l<-l+1
>             finmientras
>         finsi
>       finpara
>       k<-k+1
> finmientras
> 
> Pta: no me manden código en perl, que no conosco, en todo caso en awk....
> 
> Saludos Horacio.
> _______________________________________________
> Programacion mailing list
> Programacion@lugro.org.ar
> http://www.lugro.org.ar/mailman/listinfo/programacion