Estoy trabajando en una aplicación Java que necesita trabajar en matrices muy grandes. Por ejemplo, ¡multiplicando dos matrices de 10 millones * 10 millones! Por supuesto, el montón de Java no tiene suficiente espacio incluso para almacenar una de estas matrices. ¿Qué debo hacer? ¿Debo usar bases de datos para almacenar mis matrices y llevar a la memoria cada parte necesaria y multiplicarla parte tras otra?Manejar una gran estructura de datos en Java
considerar el uso de una base de datos de memoria como http://hsqldb.org/
Este es un RDB. ¿Quiere decir que puedo usar cualquier RDB para este significado ... por ejemplo MySQL? ¿Es eficiente usar un DB? Es decir, ¿hay alguna solución mejor (usando espacio en disco o ...). – user78564
Diría DB "incrustado", porque HSQLDB puede hacer mucho más que bases de datos en la memoria pura. –
@unknown: sí, una RDB es probablemente una buena idea para esto, ya que está diseñada para manejar grandes cantidades de datos. Dependiendo de sus necesidades exactas, es posible que necesite un software más especializado, pero a partir de lo que escribió, sugeriría una base de datos relacional. –
bien si se ven obligados a utilizar Java y no se puede escribir el código que se ocupa de estos métodos como nativos (es decir, por contar Java para llamar a un código C en vez) entonces la cosa más eficiente sería usar un archivo binario simple. Me mantendría alejado de las bases de datos en este caso porque son más lentos que el acceso directo a archivos y no necesita las características que ofrecen.
La complejidad de la multiplicación de matrices, si se lleva a cabo ingenuamente, es O (n^3), pero existen algoritmos más eficientes. De todos modos, para una matriz de 10 millones * 10 millones esto llevará mucho tiempo y es posible que se enfrente al mismo montón de probelmas pero con recursividad.
Si te gustan las matemáticas complejas, puedes encontrar herramientas para ayudarte en this article.
Eche un vistazo a hadoop.
Dado que este es un cálculo tan grande, creo que se encontrará con problemas de rendimiento junto con sus problemas de almacenamiento. Entonces, analizaría la posibilidad de paralelizar este problema y obtener múltiples máquinas/núcleos para procesar un subconjunto de datos.
Afortunadamente, una solución de multiplicación de matriz se descompondrá naturalmente. Pero estaría buscando alguna forma de grilla o solución informática distribuida.
Utilice cualquier algoritmo de matriz dispersa que se aplique a sus datos. (suponiendo que no tiene 2.4 PB de espacio en disco para contener 3 matrices de dobles cuadradas no dispersas de 10^8, y mucho menos esa cantidad de RAM para una base de datos en memoria - Blue Gene/Q 'solo' tiene 1.6 PB.)
Para consultar todas CGL-MapReduce http://www.cs.indiana.edu/~jekanaya/cglmr.html#Matrix_Multiplication
Trate de usar Memory Mapped File mediante el almacenamiento de todos los datos en un archivo externo y acceder a ella a través del objeto FileChannel.
Consulte this article para una breve introducción a MMF.
En primer lugar, una matriz de 10 millones x 10 millones es simplemente enorme. Suponiendo que se dupliquen para cada celda y no se almacene en exceso, cada una de estas cosas será de 800 terabytes. Solo leer cada celda una vez más desde la memoria principal (si de alguna manera encaja mágicamente allí, lo que claramente no está sucediendo), tomaría días. Hacerlo desde cualquier tipo de SAN plausible (lo pondremos en 10GbE) es más probable que sea meses. Y ninguna matriz multiplicada tiene O (n) complejidad - los enfoques normales son O (n^3). Entonces ... no está haciendo esto con archivos mapeados en la memoria, bases de datos comunes, ni nada por el estilo.
Código que hace algo como esto va a vivir o morir en la eficiencia de caché, donde "caché" incluye hacer un buen uso de la memoria principal, las unidades de disco locales. Dado que cualquier interfaz de almacenamiento que contenga más de una matriz de 800 terabytes seguramente será una SAN de algún tipo, es casi seguro que involucre servidores múltiples que lean y trabajen en diferentes partes de la misma.
Existen muchas formas conocidas de paralelizar la multiplicación de matrices (esencialmente multiplicar submatrices de varios tamaños y luego combinar los resultados) y cambiar el diseño para que los patrones de acceso tengan una localidad de caché razonable organizando los datos alrededor de space-filling curves en lugar de arreglos de fila/columna. Seguramente querrá ver las interfaces y diseño clásicos LAPACK, Intel's MKL, GotoBLAS como implementaciones de las funciones BLAS ajustadas a hardware moderno específico, y después de eso probablemente se está aventurando en un territorio inexplorado :-)
Es la matriz dispersa por casualidad? – TrayMan
sí. puede ser en muchos casos. pero no podemos estar seguros. – user78564
¿Qué estás tratando de lograr? Es muy probable que esta no sea la forma correcta de hacerlo. – starblue