Gérer une grande structure de données en Java

Question

Je travaille sur une application Java qui nécessite de travailler sur de très grandes matrices. Par exemple en multipliant deux 10 millions * 10 millions de matrices! Bien sûr, le tas Java n'a pas assez d'espace même pour stocker une de ces matrices. Que dois-je faire? Devrais-je utiliser des bases de données pour stocker mes matrices et mettre en mémoire toutes les parties nécessaires et les multiplier les unes après les autres?

Answer 1

envisager d'utiliser un db mémoire comme http://hsqldb.org/

Answer 2

Eh bien, si vous êtes obligé d'utiliser Java et ne peut pas écrire le code qui traite de ces méthodes comme natives (qui est, en racontant Java d'appeler un code C à la place) alors la chose la plus efficace à faire serait d'utiliser un simple fichier binaire. Je resterais loin des bases de données dans ce cas parce qu'ils sont plus lents que l'accès direct aux fichiers et que vous n'avez pas besoin des fonctionnalités qu'ils offrent.

Answer 3

La complexité de la multiplication matricielle, si elle est effectuée naïvement, est O (n^3), mais des algorithmes plus efficaces existent. Quoi qu'il en soit, pour une matrice de 10 millions * 10 millions, cela va prendre beaucoup de temps et vous risquez de faire face au même problème, mais avec une récursivité.

Si vous êtes dans les mathématiques complexes, vous pouvez trouver un outil pour vous aider dans this article.

Answer 4

Jetez un oeil à hadoop.

Answer 5

Étant donné que ce calcul est énorme, je pense que vous allez rencontrer des problèmes de performance à côté de vos problèmes de stockage. Donc, je chercherais à paralléliser ce problème et à obtenir des machines/cœurs multiples pour traiter un sous-ensemble de données.

Heureusement, une solution de multiplication matricielle se décomposera naturellement. Mais je regarderais une forme de grille ou une solution informatique distribuée.

Answer 6

Utilisez l'algorithme de matrice simple appliqué à vos données. (en supposant que vous n'avez pas 2.4 PB d'espace disque pour contenir 3 matrices non doubles de 10^8 carrés de doubles, et encore moins de RAM pour une base de données en mémoire - Blue Gene/Q 'only' a 1.6 PB.)

Answer 7

Jetez un oeil à CGL-MapReduce http://www.cs.indiana.edu/~jekanaya/cglmr.html#Matrix_Multiplication

Answer 8

Essayez d'utiliser Memory Mapped File en stockant toutes vos données dans un fichier externe et d'y accéder via l'objet FileChannel.

Consultez la section this article pour une brève présentation de MMF.

Answer 9

Tout d'abord, une matrice de 10 millions x 10 millions est simplement énorme. En supposant des doublons pour chaque cellule et aucune surcharge de stockage, chacune de ces choses va être de 800 téraoctets. Il suffit de lire chaque cellule une fois de plus dans la mémoire principale (si cela se produit magiquement, ce qui ne se produit manifestement pas), cela prendrait des jours. Le faire à partir de n'importe quel type de SAN plausible (nous le mettrons sur 10GbE) est plus susceptible d'être des mois. Et aucune multiplication matricielle n'a une complexité O (n) - les approches normales sont O (n^3). Donc ... vous ne le faites pas avec des fichiers mappés en mémoire, des bases de données communes ou quoi que ce soit de ce genre. Code faisant quelque chose comme ceci va vivre ou mourir sur l'efficacité du cache, où "cache" comprend une bonne utilisation de la mémoire principale, les lecteurs de disque locaux. Étant donné que toute interface de stockage contenant plus d'une matrice de 800 téraoctets est forcément un SAN, il est presque certain que plusieurs serveurs lisent et travaillent sur différentes parties de celle-ci.Il existe de nombreux moyens bien connus pour paralléliser la multiplication matricielle (essentiellement multiplier les sous-matrices de différentes tailles et ensuite combiner les résultats), et déplacer la disposition de sorte que les modèles d'accès aient une localisation de cache raisonnable en organisant les données autour de space-filling curves au lieu des arrangements de rangée/colonne. Vous allez certainement vouloir regarder les interfaces classiques LAPACK et la conception, Intel's MKL, GotoBLAS comme les mises en œuvre des fonctions BLAS accordées à un matériel moderne spécifique, et après que vous vous aventurez probablement en territoire inexploré :-)