Programación General > Visual C++

 Re: Matrices Esparcidas

(1/2) > >>

thebeast:
Buenas yo soy nuevo en este forum y no sabia dond poner este post yo creo q no es aqui lo siento pero es que necsito ayuda sobre Matrices Esparcidas alguien me prodria dar ejemplo o algo q me explique matrices esparcidas.

Mollense:
Hola thebeast.

Bienvenido al foro.


--- Citar ---Una matriz esparcida es una matriz en la cual la mayoría de los elementos son 0. Es un desperdicio almacenar estas matrices completas puesto que muy pocos elementos contienen información significativa.
Una forma eficiente de representar una matriz esparcida m x n es un arreglo k x 3, donde K es el número de elementos significativos. En ese arreglo se almacena el índice de la fila, el índice de la columna y el valor de los elementos distintos a cero de la matriz original. Esto se denomina una representación reducida. Por ejemplo, la matriz:
--- Fin de la cita ---

Un saludo

thebeast:
gracias por haberme respondido pero eso yo ya lo sabia por lo q e medio podido investigar pero  necsito son ejemplos sencillos en c++ para ver como funcionan y entender mucho mejor matris espacidas o mas teoria.

Mollense:
Pero si es muy sencillo, mirá...

Si tuvieras por ejemplo esta matriz:
--- Código: Text ---0 0 0 0 5 0 0 0 6 0 0 0 0 0 1 03 0 0 0 0 0 0 5 0 0 0 0 0 0 1 00 0 0 5 0 0 0 0 0 5 0 0 0 0 0 00 0 0 0 0 0 0 0 0 7 0 0 0 0 0 00 0 4 0 0 0 0 0 6 0 0 0 0 0 0 00 0 3 0 0 3 0 0 0 0 0 0 0 0 0 00 0 0 9 0 0 0 0 0 0 0 0 1 0 0 0 
Claramente vemos que es esparcida o dispersa por su gran porcentaje de valores nulos.
En el ejemplo, se estarían utilizando 16*7=112 locaciones de memoria para almacenar solamente 15 valores distintos de 0 que son los únicos que nos interesan.
Lo que se hace en estos casos es almacenar en 3 vectores (o un array) las coordenadas  de los valores distintos de cero y su valor.
Ej:

--- Citar ---fil:  0, 0, 0, 1, 1, 1, 2, 2 ...
col: 4, 8, 14, 0, 7, 14, 3, 9 ...
val: 5, 6, 1, 3, 5, 1, 5, 5 ...

--- Fin de la cita ---

Espero que sirva de algo, en cuanto al código si tenés alguna duda puntual, coloca lo que vallas haciendo que seguramente te vamos a ayudar.

Un saludo

hackzlatan:
Si pero esos ejemplos son muy triviales. Si alguien tiene un ejemplo de una matriz esparcida pero como estructura de datos, stilo lista enlazadas por favor publiquela en el foro asi tengan solo las primitivas

Navegación

[0] Índice de Mensajes

[#] Página Siguiente