Structure de données pour stocker des matrices creuses

Question

J'ai besoin de faire quelques opérations mathématiques sur des matrices creuses. J'ai remarqué que l'utilisation de tableaux n'est peut-être pas le moyen le plus efficace d'utiliser ma mémoire, d'autant plus que les matrices peuvent contenir plus de 200 lignes. J'ai aussi envisagé d'utiliser une liste chaînée, mais je ne suis pas sûr que ce soit mieux. Y a-t-il une structure de données appropriée [approche] à cette situation?

Answer 1

Combien de "plus de 200 lignes"? Comment rare? Une matrice de doublons de 1000x1000 est toujours inférieure à 8MB, ce qui ne m'inquiète pas sauf si vous devez travailler avec beaucoup d'entre eux simultanément.

La structure de données idéale dépend principalement du type d'opérations que vous devez effectuer. Notez qu'il existe des versions sparse matrix libraries prêtes à l'emploi pour toutes les langues courantes. Il est préférable d'utiliser l'une d'entre elles plutôt que de rouler la vôtre.

Answer 2

Voici quelques bibliothèques de mathématiques Java open source qui incluent des matrices creuses. Vous pourriez étudier les structures de données utilisées (ou même simplement en utiliser une si vous programmez en Java).

• Colt
• Jsci
• Matrix Toolkits Java

Answer 3

Il y a une nouvelle bibliothèque de matrice pour java qui ressemble à cela pourrait avoir un bon soutien Sparse Matrix: UJMP: The Universal Java Matrix Package