Foro

¡Hola buenas!

Vereis, tengo que entregar un trabajo de programación en java que básicamente es una calculadora de matrices. Estoy aquí dándole caña al blueJ y ya me echa humo y todo.

El problema que tengo es el siguiente, la matriz no puede ser un vector de vectores(vector bidimensional), ya que según dice el enunciado del trabajo ocupa mucho espacio dado que se tratará de matrices cuasi-vacias, con un máximo de 1000 elementos no nulos. La solución pasaría por programar con POO y crenado una clase matriz que tiene para cada elemento una variable para el valor del dato y dos para sus posiciones: fila y columna.

El problema lo tengo a la hora de crear el método que multiplique dos matrices A y B y me guarde el resultado en A. Ya que no se muy bien como enfocarlo.

¿Alguien podría echarme una manica?

Un saludo

Una opción facil aunque no la más rápida sería que tu objeto matriz tenga un método get(i,j) que te devuelva el valor.

Este método get sería el equivalente a un [i][j] de una matriz hecha por 2 arrays. Sería fácil que te devuelva 0 cuando i,j no existe y el valor cuando este existe. A su vez debería de lanzar una excepción si i o j están fuera de rango. Ya con dicho get podrías hacer una multiplicación como si fueran matrices normales.

Se entendió?

Yo soy mas de C# pero son la misma mierda XD

Se te permite hacer un arraylist de arraylist? eso solucionaría tus problemas de ocupar espacio de mas en memoria y te salteas la parte de pensarlo en OO XD

Yo siendo pocos valores lo que haria es recorrer los valores de la primera matriz y comprobar si existe el valor complementario.

Si el valor que tengo es el [2,1] en la primera matriz se tendra que multiplicar por el valor [1,2] y si no existe sera 0. Es coger lo que decía havelock y quizá simplificarlo un poco por que no tienes que comprobar todos los valores.

Si los valores en vez de en un array los metes en un Hashmap lo tienes echo ya que puedes conseguir que te de el valor poniendo de key las coordenadas del valor en la matriz y el valor como value.

Gracias a todos por responder. Lamentablemente el arraylist de arraylist tampoco se puede.

Me gusta lo que propone Havelock. A ver si lo he entendido, el metodo get, lo que haría sería pasarme desde el objeto matriz de cada fila y columna cada valor de esa posición, ¿no?. Y luego tendría que hacer el proceso contrario para guardarla ¿no?

Edito: lo que dice machera, solo que busco el complementario de [1,2] entre todas las keys de B que se que tienen término no nulo.

Yo de java no recuerdo ya, lo haría con diccionarios en python :)

Si tienes matrices con pocos elementos un array de arrays es ineficiente consume demasiada memoria. Este tipo de matrices ralas o sparse no es raro que tenga una cantidad de elementos distintos de cero O(n), por ejemplo matrices diagonales.

El método get lo necesitas si o si, en tu clase necesitarás un método para extraer términos de la matriz.

La multiplicación clásica es ineficiente, lo que se busca con este tipo de estructuras de datos es crear métodos en los cuales las operaciones sean proporcionales a los elementos no nulos de las matrices. La multiplicación clásica hace n^3 operaciones. En este caso el método clásico se pasa la mayoría del tiempo multiplicando ceros y sumando ceros...

Yo haría lo siguiente:
-un método get(i,j) para extraer el término i,j de la matriz
-un método set(key, value) donde key es (i,j) y value el valor i,j de la matriz, sirve para guardar un valor en el término i,j
-un método getkeys que devuelva una lista con las keys de los términos de la matriz no nulas.
-nrows para extraer el número de filas
-ncols para extraer el número de columnas

El método sería para unas matrices A y B:
- Si las matrices no tienen dimensiones compatibles lanzo excepción o error.
- Creo una matriz producto de la dimensión adecuada con todo ceros. (la lista de keys es vacía)

En pseudocódigo pythonizado

C = nueva_matriz_sparse_vacia(numero_filas, numero_columas)

Akeys = A.keys()
Bkeys = B.keys()

for clave_A in Akeys do
for clave_B in Bkeys do
si clave_A[2] == clave_B[1] entonces
clave_C = [clave_A[1], clave_B[2]]
C.set(clave_C, C.get(clave_C)+ A.get(clave_A)*B.get(clave_B) )
end si
end for
end for

Justificación: tomo las llaves no nulas de A y comparo cada llave de A con una llave de B, si la columna de clave_A coincide con la fila de clave_B entonces estos dos términos influyen en el producto, por lo que hago:

C[i,j] += A[i,k]*B[k,j]

En este caso cada par exitoso necesita hacer un producto y una suma. Por lo que el algoritmo hace como mucho 2*L1*L2 operaciones donde L1 sea la cantidad de llaves de A y L2 la cantidad de llaves de B.

Tal vez se podría optimizar el doble ciclo con algún tipo de filtro o una estructura de datos que guarde por cada fila de A las columnas que tienen términos no nulos y cada columna de A las filas no nulas. De todas formas el código se puede optimizar bastante.
Por ejemplo, según las matrices se van volviendo menos sparse en el peor de los casos se puede llegar al extremo de hacer n^4 comparaciones de keys para dos matrices tamaño nxn, ¡esto es peor que el método clásico! Pero es un comienzo.

Hace eones que deje de programar, pero a ver si puedo ayudar...

La idea de los metodos get (y sus complementarios set) es sacar informacion de los objetos sin guarrear sus variables directamente, creo que es lo que has entendido, vaya.

Lo que yo haria... Si te quieres complicar un poco la vida, inventate primero una clase de objeto "posicion", de dos enteros i,j. La matriz seria un hashmap de objetos posiciones con su valor.
Para saber si tienes ese valor en la matriz, el hashmap tiene el "containsKey(Object key)", para informarlo; el put(object key, object value); para borrarlo, el remove(Object key)...

Tengo un amigo ingeniero informático especializado en java. Puedes pasarte por su blog y tentar a la suerte xD
El blog de Alfonso Marín

Un par de comentarios.

Este no es un problema de Java. Es un problema de programación genérica.

Me da la impresión de que es un ejercicio en el cual no importa demasiado la performance si no lo habría indicado thorom en su post inicial.

Lo que dice Skoll es cierto, el algoritmo clásico de multiplicación de matrices es bastante malo pero hasta qué punto es necesario usar otro en este ejercicio? Eso ya dependerá de Thorom. En todo caso buscando en google seguro hay mucha info sobre cómo hacer multiplicaciones de matrices dispersas (sparse, con muchos 0's).

Con el algoritmo clásico:

public Matrix prod(Matrix A, Matrix B){

  if (A.columnCount() != B.rowCount()) {

    throw new RuntimeException("Las matrices deben ser MxN y NxK");

  }
  int suma = 0;
  Matrix res = new Matrix();
  for(int i = 0; i < A.rowCount(); i++){
    for(int j = 0; j < B.columnCount(); j++){
      suma = 0;
      for(int k = 0; k < A.columCount(); k++){
        suma +=A.get(i, k) * B.get(k, j);
      }
      res.set(i, j) = suma;
    }
  }
  return result;
}

Notá que es necesario tener el tamaño de las matrices, no alcanza con tener los valores existentes.

Como se dijo antes este método dista muchísimo de ser performante ya que se hacen muchas multiplicaciones por 0 pero es a mi parecer el más simple de implementar. Si preferís un método más performante yo buscaría en google, ni hablar de que probablemente ya exista una librería de que te lo resuelva pero seguro que no lo tenés permitido.

El algoritmo no está probado así que puede tener algún bug. No me hago responsable de su uso.

Cita:

Un poco dramático, no? XD

Cita:

A mi la frase me encanta XD, pero bueno soy de leyes XD.

Pues mi consejo va a ser muy diferente.

No lo busques en google. Simplemente levantate de la mesa tomate un café, ve un rato la tele, duerme. Piensa en otras cosas. Duerme un rato.

Luego vuelve al BlueJ y dale más caña. Con la cabeza limpia seguro que te sale. Y estarás aprendiendo a programar, no a buscar en google.

Javierrivera2 se sincero, aprender a programar en Java es aprender a buscar en google xD

machera: Por eso dije programar sin más ;).

Python rules ;P.

Gracias a todos, finalmente he optado por una solución parecida a la que dió havelock. Aunque modificada para el nivel que me piden, que es algo menor que eso.

Muchas gracias, repito. Me habeis ayudado mucho.

Dios...y esto es lo que me espera a mi??
Una preguntita Thorom, saliéndonos un poco del tema, el trabajo que te pedía...¿era para la universidad o algo así?

Cita:

No es tan difícil como parece, con insistencia/investigación se logra y se ven los frutos en relativamente poco tiempo, pero al principio putearas desde George Boole hasta Alan Kay XD

Juas, pues yo soy un espectro friki del java!

No puedo ayudar, pero el otro día utilizé una matriz por primera vez y me creí el rey del universo!

La ignorancia hace la felicidad

+1 al titulo XD Me causo muchisima gracia.