Matrices Gigantes
En primer lugar, programo en VC++. Te cuento; Yo soy ingeniero Eléctrico y trato de crear una aplicación con fines de cálculos de ingeniería basada en el método de los elementos finitos. He decidido programarla yo mismo ya que me encanta programar y además no tengo plata como para pagarle a un programador (Y no creo que alguien vaya a creer en mi proyecto, al menos en esta etapa, como para trabajar por ni uno). Aquí va la pregunta; Necesito generar metrices gigantescas (10.000x10.000) con tipos de datos "double" y por supuesto no me permite declarar matrices de este orden. Una vez en una reunión de amigos me encontré con un Ing. Informático y le pregunte y mi novia me reto por andar preguntando esas c osas en reuniones sociales y creo que estaba complicando al tipo de todas maneras. Bueno lo que he logrado entender leyendo y preguntando es que tengo que crear una estructura de datos dinámica (con punteros) y reservar grandes cantidades de memoria ram para almacenarla, o algo así. Pero yo saco estas cuentas; Una matriz de 10.000x10.000 son 10^8 datos un double ocupa creo que 4 Bytes y luego 4x10^8 = 4000 MB y mi PC solo tiene 64MB, entonces antes de ponerme a programar esa estructura pienso en ese predicamento. ¿Y ahora quien podrá ayudarme?... Te cuento que también estoy trabajando con Open GL para la creación de los gráficos 3D. Y en eso me ha ido bien en general no he tenido problemas y pienso crear un humilde articulo para enviarlo a la página. Si te interesa puedo enviarte mi trabajo cuando lo termine.
PD: Esas barras de herramientas flotantes con un botoncito de cerrar pequeñito, ¿solo se pueden crear con MFC?
Muy bien Doctor, espero no ofuscarle con estas trivialidades, y desde ya muy agradecido espero su respuesta. Cualquier información me será de gran utilidad.
Sinceramente.
Rodrigo
PD: Esas barras de herramientas flotantes con un botoncito de cerrar pequeñito, ¿solo se pueden crear con MFC?
Muy bien Doctor, espero no ofuscarle con estas trivialidades, y desde ya muy agradecido espero su respuesta. Cualquier información me será de gran utilidad.
Sinceramente.
Rodrigo
5 Respuestas
Respuesta de chirri
1
Te voy a comentar como lo veo, aunque no lo tomes al pie de la letra.
Yo te comento y luego, tú, que sabes al problema que te enfrentas sabrás
si es útil lo que te comento.
Las cuentas que he realizado de lo que ocupa una matriz de
10.000x10.000 de tipo double, me sale un resultado distinto al tuyo.
Un dato tipo double ocupa 8 bytes y de tipo float 4 bytes.
10.000x10.000=10^8 bytes. Esto sería si cada dato o elemento de
la matriz ocupara un byte. Como estamos con una matriz de double
( 8 bytes), hacemos 8*10^8 bytes ocupa la matriz. Ahora pasamos
este valor a Megabytes.
Siguiendo una regla de tres:
1024 bytes ----- 1Kbyte
8*10^8bytes--- x
x = 8*10^8/1024 = 781250 Kbytes.
Y ahora de Kbytes a megas.
1024 Kbytes ----- 1Megabyte
781250 ----- x
x = 781250 / 1024 = 762.93 Megabytes. ==> 763 Mb.
Entonces tenemos una matriz que ocupa 763 megas. ¿Y qué maquina
normalita tiene ese cantidad de RAM? No he visto ninguna.
Entonces lo único que se ocurre es:
1.- ¿Es posible partir ese matriz, en matrices más pequeñas y luego
combinar los resultados de esas matrices pequeñas?
2.- Crear en disco un fichero binario que represente la matriz. Esto
haría que los cálculos fuesen mucho más lento. Sería:
...
// crear matriz gigante.
fp=fopen("matriz.dat","wb");
for(i=0;i<10000;j++)
{
for(j=0;j<10000;j++)
{
fwrite(&data,sizeof(double),1,fp);
}
}
fclose(fp);
Para acceder a un elemento.
double getMatrixData(int i,int j,FILE *fp)
{
double data;
long offset;
// i represnta las filas y j las columnas
// ===> j
// -------------------------
// |
// i |
// |
offset = sizeof(double)*(i*10000)+j;
fseek(fp,SEEK_SET);
fread(&data,sizeof(double),1,fp);
return data;
}
Para aumentar la velocidad habría que optimizar el rendimiento posiblemente
con una matriz intermedia en memoria. Como si puera un matriz cache.
Y si se realizan cálculos que durante un tiempo son independientes entre si.
Realizar eses cálculos con programación multithread ( concurrente ). Es
decir, tener varios hilos de ejecución para realizar los cálculos.
Respecto a lo la toolbar, todo lo que he vista usa mfc. Pero si
encontró alguna forma ya te lo comentaré.
Yo te comento y luego, tú, que sabes al problema que te enfrentas sabrás
si es útil lo que te comento.
Las cuentas que he realizado de lo que ocupa una matriz de
10.000x10.000 de tipo double, me sale un resultado distinto al tuyo.
Un dato tipo double ocupa 8 bytes y de tipo float 4 bytes.
10.000x10.000=10^8 bytes. Esto sería si cada dato o elemento de
la matriz ocupara un byte. Como estamos con una matriz de double
( 8 bytes), hacemos 8*10^8 bytes ocupa la matriz. Ahora pasamos
este valor a Megabytes.
Siguiendo una regla de tres:
1024 bytes ----- 1Kbyte
8*10^8bytes--- x
x = 8*10^8/1024 = 781250 Kbytes.
Y ahora de Kbytes a megas.
1024 Kbytes ----- 1Megabyte
781250 ----- x
x = 781250 / 1024 = 762.93 Megabytes. ==> 763 Mb.
Entonces tenemos una matriz que ocupa 763 megas. ¿Y qué maquina
normalita tiene ese cantidad de RAM? No he visto ninguna.
Entonces lo único que se ocurre es:
1.- ¿Es posible partir ese matriz, en matrices más pequeñas y luego
combinar los resultados de esas matrices pequeñas?
2.- Crear en disco un fichero binario que represente la matriz. Esto
haría que los cálculos fuesen mucho más lento. Sería:
...
// crear matriz gigante.
fp=fopen("matriz.dat","wb");
for(i=0;i<10000;j++)
{
for(j=0;j<10000;j++)
{
fwrite(&data,sizeof(double),1,fp);
}
}
fclose(fp);
Para acceder a un elemento.
double getMatrixData(int i,int j,FILE *fp)
{
double data;
long offset;
// i represnta las filas y j las columnas
// ===> j
// -------------------------
// |
// i |
// |
offset = sizeof(double)*(i*10000)+j;
fseek(fp,SEEK_SET);
fread(&data,sizeof(double),1,fp);
return data;
}
Para aumentar la velocidad habría que optimizar el rendimiento posiblemente
con una matriz intermedia en memoria. Como si puera un matriz cache.
Y si se realizan cálculos que durante un tiempo son independientes entre si.
Realizar eses cálculos con programación multithread ( concurrente ). Es
decir, tener varios hilos de ejecución para realizar los cálculos.
Respecto a lo la toolbar, todo lo que he vista usa mfc. Pero si
encontró alguna forma ya te lo comentaré.
Querido amigo, me has dejado pasmado con tu increíble elocuencia e iluminación, digna de las mentes más privilegieda. Tu análisis es muy claro y sencillo y deja explicado de manera impecable el error en que su servidor había incurrido. Lo de los 1024 bytes no lo había considerado para nada y eso que alguna vez lo vi en el libro de Shildt. Tampoco había considerado la posibilidad de multiproceso, ya que mis conocimientos en esa área son pobres. Todo esto me hace pensar en que sin ninguna duda debo estudiar más. Lo de la posibilidad de trabajar con submatrices lo estoy consultando a los expertos matemáticos, espero con mucha esperanza, que estos circunspectos señores tengan algún teorema bajo la manga. Si es así, yo creo que voy a tener que chuparles el cuerpo, aunque se vea un poco indecoroso. Lo que más me anima en estos momentos es haberme dado cuenta de que el espacio que necesito en disco para trabajar en sensiblemente menor al que había mal calculado en primera instancia, sin lugar a duda y a pesar de seguir siendo un valor respetable es mucho más razonable. Tu orientación me ha sido de gran utilidad y agradezco con vehemencia tu importante aporte a esta humilde causa.
Sinceramente
Rodrigo
Sinceramente
Rodrigo
Respuesta de vider
1
Contestando a tu pregunta, no te recomiendo que crees un área de memoria tan grande en un equipo con tan poca memoria ram, puedes crearla aumentando el swap al tamaño que necesitas, (emulación de memoria RAM que se escribe en disco duro), te recomiendo que crees directamente un fichero en disco asignando el tamaño que necesitas, después podrás acceder directamente a las posiciones del mismo con tus datos.
A la segunda pregunta, las ventanas las crea Windows directamente, las MFC son un interface simplificado al API (Aplication Programing Interface) de Windows, por lo que es posible crearlas sin recurrir a las mfc (son dialog box con el estilo extendido TOOLWINDOW), te recomiendo que consigas el Microsoft Windows SDK y el MSDN, el primero trae multidud de ejemplos de creación de ventanas, controles de windows, APIS específicos, etc y en el segundo puedes encontrar gran cantidad de información técnica, artículos y ejemplos sobre MFC y programación en Windows.
Un Saludo, no dudes en escribirme para cualquier duda
José Luis Rey
A la segunda pregunta, las ventanas las crea Windows directamente, las MFC son un interface simplificado al API (Aplication Programing Interface) de Windows, por lo que es posible crearlas sin recurrir a las mfc (son dialog box con el estilo extendido TOOLWINDOW), te recomiendo que consigas el Microsoft Windows SDK y el MSDN, el primero trae multidud de ejemplos de creación de ventanas, controles de windows, APIS específicos, etc y en el segundo puedes encontrar gran cantidad de información técnica, artículos y ejemplos sobre MFC y programación en Windows.
Un Saludo, no dudes en escribirme para cualquier duda
José Luis Rey
Muchísimas Gracias tu respuesta me ha sido de gran utilidad, orientándome en el camino a seguir. Con lo del swap eso si me dejaste pillo, voy a ponerme a investigar como loco sobre ese tema. Eso si ahora pienso. Voy a tener que decir que mi aplicación requiere 4 GB de espacio libre como mínimo para funcionar, ¿no habrá alguna forma de comprimir los datos?
Gracias.
Gracias.
Respuesta de cover
1
He visto tu pregunta y las respuestas de algunos expertos te han aportado. Mi granito de arena no tiene la misma tendencia que la del resto, me explico.
Es una tontería en pensar ampliar la memoria física o virtual para solucionar este problema. Una pregunta que quiero que te respondas, ¿cómo funciona la paginación por demanda (memoria virtual)? Pues mi solución va por ahí. No sé la finalidad de los cálculos que vas a aplicar sobre tu macromatriz, pero si a priori supieras cuales son, pues podrías crearte una rutina que trabajando con submatrices (asequibles) obtenidas de la grande y realizando tus cálculos llegarías a la solución final.
Por tanto mi solución es dividir la macromatriz en matrices de tamaño moderado y trabajar sobre estas, una vez calculadas agruparlas y así obtener la solución final. Nunca pienses en una única vía para tu solución (que en este caso es un poco bestia), suerte y espero que te halla servido de ayuda.
Es una tontería en pensar ampliar la memoria física o virtual para solucionar este problema. Una pregunta que quiero que te respondas, ¿cómo funciona la paginación por demanda (memoria virtual)? Pues mi solución va por ahí. No sé la finalidad de los cálculos que vas a aplicar sobre tu macromatriz, pero si a priori supieras cuales son, pues podrías crearte una rutina que trabajando con submatrices (asequibles) obtenidas de la grande y realizando tus cálculos llegarías a la solución final.
Por tanto mi solución es dividir la macromatriz en matrices de tamaño moderado y trabajar sobre estas, una vez calculadas agruparlas y así obtener la solución final. Nunca pienses en una única vía para tu solución (que en este caso es un poco bestia), suerte y espero que te halla servido de ayuda.
Muchísimas Gracias. He leído con atención tu consejo y justamente ayer, mientras estaba en el baño sumido en ondas meditaciones comencé a acariciar la idea y seguí pensando en eso (dividir la matriz en otras más pequeñas), incluso me las quise dar de matemático y empecé aprobar cosas y cuando llegue a las matrices de 5x5 me frustré porque no concluí nada. Sin embargo, considerando que la matriz es simétrica aij=aji y que además todos los eleméntos de la diagonal son identicos a11=a22=a33...=ann. Pienso que debería existir una forma de trabajar con submatrices. Para serte sincero aprobé álgebra lineal con un 4.5. Tu orientación me ha animado a preguntarle a los expertos matemáticos, estos conspicuios y simpáticos señores de lo abstracto. Ellos deben tener alguna teorema que desconozco.
Agradezco mucho tu atención.
Sinceramente
Rodrigo
Agradezco mucho tu atención.
Sinceramente
Rodrigo
Respuesta de paufr
1
Antes que nada perdona por el retraso.
Bueno tu problema es uno de los más gordos de la informática. Ante de abordarlo debes evaluar el tanto por cien de elementos de la matriz que van a ser 0. Me explico, en muchos cálculos matemáticos la mayor parte de la información se centra en la diagonal principal, o al algún otro sitio, siendo la mayoría de los números 0. Si este es tu caso tiene solución. Estas en el típico caso de matriz dispersa. Te aconsejo que busques componentes para trabajar con este tipo de matrices. Mejor que no lo hagas directamente por que requiere grandes conocimientos matamaticos e informáticos.
Ah! Y un double no ocupa 4 bytes, típicamente ocupa 8 bytes. Pero depende de lenguaje de programación
Lo del botoncito no lo se.
Bueno tu problema es uno de los más gordos de la informática. Ante de abordarlo debes evaluar el tanto por cien de elementos de la matriz que van a ser 0. Me explico, en muchos cálculos matemáticos la mayor parte de la información se centra en la diagonal principal, o al algún otro sitio, siendo la mayoría de los números 0. Si este es tu caso tiene solución. Estas en el típico caso de matriz dispersa. Te aconsejo que busques componentes para trabajar con este tipo de matrices. Mejor que no lo hagas directamente por que requiere grandes conocimientos matamaticos e informáticos.
Ah! Y un double no ocupa 4 bytes, típicamente ocupa 8 bytes. Pero depende de lenguaje de programación
Lo del botoncito no lo se.
Muchas gracias por tu atencón, la verdad, he recibido muchos consejos y no sabía que me estaba enfrentando a un problema gordo de informática. La verdad es que mi política es que si no lo se, lo aprendo y si me va a tomar 10 año aprender todo lo que necesito, entonces lo voy a aprender en 10 años, y en ese sentido soy extremadamente terco y perseverante. Lo de los componentes no lo había escuchado, ¿de qué se trata? ¿Me puedes dar más información?
Sinceramente
Rodrigo
Sinceramente
Rodrigo
Respuesta de corday
1
En primer lugar siento haber tardado tanto tiempo en responder.
Realmente es un problema querer calcular este tpo de matrices enormes, para llevarlo a cabo solo se me ocurren dos vías:
1. Agilizar el calculo mediante el calculo de matrices más pequeñas (de algún modo no se si esto seria posible) es decir, dividir el problema en matrices menores porque es complicado manejar con matrices tan grandes.
2. Trabajar con matrices dinámicas usando punteros, Puesto que no puedes almacenar toda la matriz en memoria tendrías que guardar la matriz en un fichero e ir operando poco a poco con la cantidad que te permita la memoria.
Espero haberte sido de ayuda,
un saludo. Juan
Realmente es un problema querer calcular este tpo de matrices enormes, para llevarlo a cabo solo se me ocurren dos vías:
1. Agilizar el calculo mediante el calculo de matrices más pequeñas (de algún modo no se si esto seria posible) es decir, dividir el problema en matrices menores porque es complicado manejar con matrices tan grandes.
2. Trabajar con matrices dinámicas usando punteros, Puesto que no puedes almacenar toda la matriz en memoria tendrías que guardar la matriz en un fichero e ir operando poco a poco con la cantidad que te permita la memoria.
Espero haberte sido de ayuda,
un saludo. Juan
Juan
Primero que nada quiero agradecer tu interés y tu deferencia al contestar mi pregunta. Lo de trabajar con submatrices lo vengo pensando hace tiempo y aquí en todoexpertos me han sugerido lo mismo. ¿El problema es como? No soy experto en matemáticas y desocosco los misterios del álgebra lineal. Es por eso que recurro a Uds. Los expertos en matemáticas. Yo se que las matemáticas son muy extensas y que por lo general uno se especializa en ciertos temas. Ya que no se puede ser experto en todas las áreas de las matemáticas. Tengo además bien afinado el algoritmo para trabajar con una matriz gigante en disco e ir cargando las filas que necesito en RAM para realizar las operaciones. Mi Problema es; Como hacer para no tener que cargar esa enorme matriz en el disco. Es decir, busco algún método para reducir el espacio simultáneo en el disco ya que las fórmulas con que calculo los elementos de la matriz son recursivas y consumen mucho tiempo estoy dispuesto a sacrificar tiempo de calculo por disminuir el espacio en disco. ¿Cómo te decía recién el problema es como trabajar con submatrices? ¿Existirá algún teorema aplicable a las matrices simétericas?
Si tienes alguna información que pueda ayudarme, cualquier cosa, no dudes en enviármela por correo a [email protected] y yo prometo enviarte la librería de clases en C++ con documentación y todo para cuando la termine. Nuevamente agradezco tu desinteresado aporte y te deseo suerte en todo lo que emprendas.
Sinceramente
Rodrigo
Primero que nada quiero agradecer tu interés y tu deferencia al contestar mi pregunta. Lo de trabajar con submatrices lo vengo pensando hace tiempo y aquí en todoexpertos me han sugerido lo mismo. ¿El problema es como? No soy experto en matemáticas y desocosco los misterios del álgebra lineal. Es por eso que recurro a Uds. Los expertos en matemáticas. Yo se que las matemáticas son muy extensas y que por lo general uno se especializa en ciertos temas. Ya que no se puede ser experto en todas las áreas de las matemáticas. Tengo además bien afinado el algoritmo para trabajar con una matriz gigante en disco e ir cargando las filas que necesito en RAM para realizar las operaciones. Mi Problema es; Como hacer para no tener que cargar esa enorme matriz en el disco. Es decir, busco algún método para reducir el espacio simultáneo en el disco ya que las fórmulas con que calculo los elementos de la matriz son recursivas y consumen mucho tiempo estoy dispuesto a sacrificar tiempo de calculo por disminuir el espacio en disco. ¿Cómo te decía recién el problema es como trabajar con submatrices? ¿Existirá algún teorema aplicable a las matrices simétericas?
Si tienes alguna información que pueda ayudarme, cualquier cosa, no dudes en enviármela por correo a [email protected] y yo prometo enviarte la librería de clases en C++ con documentación y todo para cuando la termine. Nuevamente agradezco tu desinteresado aporte y te deseo suerte en todo lo que emprendas.
Sinceramente
Rodrigo