Quelle est la meilleure structure de données que je puisse utiliser pour ma matrice contenant des variables courtes, mais la plupart des éléments sont vides ..
Je pourrais simplement utiliser N par b tableau pour la matrice, mais le problème est que je ne veux pas perdre la mémoire car seuls quelques éléments sont dans la matrice ..
J'allais utiliser une liste liée ou une table de hachage mais que vous n'êtes pas sûr de savoir lequel serait la meilleure structure de données et comment la mettre en œuvre ..
3 Réponses :
Lorsque la matrice est rare, il est préférable d'utiliser LinkedList. LinkedList sera mieux que d'autres options en termes d'espace (à condition que la matrice soit clairsemée).
Mais notez que LinkedList a O (n) Temps d'accès.
Je voudrais mettre en œuvre un Matrix clairsemé . Utilisez un hashmap avec l'index de ligne sous forme de touches, puis un hashmap ou treemap pour les éléments réels (avec l'index de la colonne comme clé) . Si vous stockez des types primitifs, je vous suggère de regarder le Trove Cadre de collections Java. Il est optimisé pour une utilisation avec des types primitifs. Je suggérerais de l'utiliser de toute façon, car les clés pouvaient être primitives.
Cela pourrait aider pour les matrices rares dans Java Stackoverflow.com/Questtions / 390181 / ... Si vous allez rouler le vôtre, je pense que le choix de la structure de données dépendrait de quel type d'opérations vous ferez