Alternatives HashMap pour le stockage de données à mémoire efficace

Question

J'ai actuellement un programme de type tableur qui conserve ses données dans une ArrayList de HashMaps. Vous serez sans doute choqué quand je vous dis que cela ne s'est pas avéré idéal. La surcharge semble utiliser 5 fois plus de mémoire que les données elles-mêmes.

This question demande à propos des bibliothèques de collections efficaces, et la réponse a été utiliser Google Collections. Mon suivi est "quelle partie?". J'ai lu la documentation mais je n'ai pas l'impression que cela donne une très bonne idée des classes qui conviennent le mieux. (Je suis également ouvert à d'autres bibliothèques ou suggestions). Je recherche donc quelque chose qui me permettra de stocker des données de type feuille de calcul dense avec un minimum de mémoire.

• Mes colonnes sont actuellement référencés par des objets sur le terrain, des lignes par leurs index, et les valeurs sont des objets, presque toujours des chaînes
• Certaines colonnes auront beaucoup de valeurs répétées
• opérations principales sont à mettre à jour ou supprimer enregistrements basés sur les valeurs de certains champs, ainsi que l'ajout/suppression/combinaison de colonnes

Je connais des options comme H2 et Derby mais dans ce cas, je ne cherche pas à utiliser une base de données intégrée.

EDIT: Si vous suggérez des bibliothèques, j'apprécierais également si vous pourriez me diriger vers une classe particulière ou deux qui s'appliqueraient ici. Alors que la documentation de Sun contient généralement des informations sur les opérations O (1), O (N), etc., je ne vois pas grand-chose dans les bibliothèques tierces, ni vraiment de description des classes qui conviennent le mieux à ce que .

Answer 1

Donc, je suppose que vous avez une carte de Map<ColumnName,Column>, où la colonne est en fait quelque chose comme ArrayList<Object>.

Quelques possibilités -

• Etes-vous tout à fait sûr que la mémoire est un problème? Si vous êtes généralement inquiet au sujet de la taille, il vaudrait la peine de confirmer que ce sera vraiment un problème dans un programme en cours. Il faut énormément de lignes et de cartes pour remplir une JVM.

• Vous pouvez tester votre ensemble de données avec différents types de cartes dans les collections. En fonction de vos données, vous pouvez également initialiser des cartes avec des combinaisons de taille/facteur de charge prédéfinies qui peuvent vous aider. Je me suis trompé dans le passé, vous pourriez obtenir une réduction de 30% de la mémoire si vous êtes chanceux. Qu'en est-il du stockage de vos données dans une structure de données matricielle unique (une implémentation de bibliothèque existante ou quelque chose comme un wrapper autour d'une liste de listes), avec une seule carte qui mappe les clés de colonne aux colonnes matricielles?

Answer 2

Certaines colonnes auront beaucoup de valeurs répétées

suggère immédiatement me l'utilisation possible du FlyWeight pattern, quelle que soit la solution que vous choisissez pour vos collections.

Answer 3

collections Trove devraient avoir un soin particulier sur l'espace occupé (je pense qu'ils ont adapté les structures de données si vous vous en tenez à des types primitifs) .. jeter un oeil here.

Sinon, vous pouvez essayer avec Apache collections .. juste faire vos repères!

anycase En, si vous avez de nombreuses références autour de mêmes éléments tentent de concevoir un certain modèle adapté (comme flyweight)

Answer 4

conserve ses données dans un ArrayList de HashMaps
Eh bien, cette partie semble terriblement inefficace pour moi. HashMap vide alloue déjà 16 * size of a pointer octets (16 correspond à la capacité initiale par défaut), plus quelques variables pour l'objet de hachage (14 + psize). Si vous avez beaucoup de lignes vides, cela pourrait être un gros problème.

Une option consisterait à utiliser un seul hachage volumineux avec une clé composite (combinaison de ligne et de colonne). Bien que cela ne rende pas les opérations sur des lignes entières très efficaces.

En outre, puisque vous ne mentionnez pas l'opération d'ajout de cellule, vous pouvez créer des hachages avec uniquement le stockage interne nécessaire (paramètre initialCapacity). Je ne connais pas beaucoup de google collections, donc je ne peux pas aider là-bas. En outre, si vous trouvez une optimisation utile, veuillez poster ici! Ce serait intéressant de savoir.

Answer 5

D'après votre description, il semble qu'au lieu d'un ArrayList de HashMaps que vous voulez plutôt un (lié) HashMap de ArrayList (chaque ArrayList serait une colonne).

Je voudrais ajouter une double carte de nom de champ à numéro de colonne, et certains getters/setters intelligents qui ne jettent jamais IndexOutOfBoundsException.

Vous pouvez également utiliser un ArrayList<ArrayList<Object>> (fondamentalement une matrice en croissance dinamiquement irrégulière) et conserver le mappage sur les noms de champs (colonnes) à l'extérieur.

Certaines colonnes auront beaucoup de valeurs répétées

Je doute cette question est importante, surtout si elles sont des chaînes, (ils sont internalisés) et votre collection entreposaient des références à leur disposition.

Answer 6

Gava inclut une interface Table et une implémentation basée sur le hachage. On dirait un ajustement naturel à votre problème. Notez que ceci est toujours marqué comme bêta.

Answer 7

En supposant que toutes vos lignes contiennent la plupart des mêmes colonnes, vous pouvez simplement utiliser un tableau pour chaque ligne et un < ColumnKey, Integer> pour rechercher quelles colonnes font référence à quelle cellule. De cette façon, vous avez seulement 4 à 8 octets de frais généraux par cellule.

Si les chaînes sont souvent répétées, vous pouvez utiliser un pool de chaînes pour réduire la duplication des chaînes. Les pools d'objets pour d'autres types immuables peuvent être utiles pour réduire la mémoire consommée.

EDIT: Vous pouvez structurer vos données en fonction de la ligne ou de la colonne.Si ses lignes basées (un tableau de cellules par ligne) ajouter/supprimer la ligne est juste une question de supprimer cette ligne. Si ses colonnes sont basées, vous pouvez avoir un tableau par colonne. Cela peut rendre la manipulation des types primitifs beaucoup plus efficace. c'est-à-dire que vous pouvez avoir une colonne qui est int [] et une autre qui est double [], c'est beaucoup plus commun pour une colonne entière d'avoir le même type de données, plutôt que d'avoir le même type de données pour une ligne entière. Toutefois, dans les deux cas, vous pouvez optimiser les données, il sera optimisé pour une modification de ligne ou de colonne et pour effectuer un ajout/suppression de l'autre type entraînera une reconstruction de l'ensemble de données entier.

(Ce que je fais est d'avoir des données en ligne et d'ajouter des colonnes à la fin, en supposant qu'une ligne n'est pas assez longue, la colonne a une valeur par défaut, cela évite une reconstruction lors de l'ajout d'une colonne. colonne, j'ai un moyen de l'ignorer)

Answer 8

J'ai expérimenté avec l'utilisation du SparseObjectMatrix2D du projet Colt. Mes données sont assez denses mais leurs classes Matrix n'offrent vraiment aucun moyen de les agrandir, donc je suis allé avec un ensemble de matrice clairsemée à la taille maximale.

Il semble utiliser environ 10% moins de mémoire et charge environ 15% plus vite pour les mêmes données, tout en offrant des méthodes de manipulation intelligentes. Toujours intéressé par d'autres options cependant. Pourquoi n'essaieriez-vous pas d'implémenter le cache comme EHCache?

Answer 9

Cela s'est avéré très efficace pour moi, quand j'ai eu la même situation.
Vous pouvez simplement stocker votre collection dans l'implémentation EHcache. Il existe des configurations telles que:

Maximum bytes to be used from Local heap. 

Une fois les octets utilisés par vos déversoirs d'application qui configurés dans le cache, puis la mise en œuvre du cache prend en charge l'écriture des données sur le disque. Vous pouvez également configurer la durée après laquelle les objets sont écrits sur le disque en utilisant l'algorithme Least Recent Used. Vous pouvez être sûr d'éviter toute erreur de mémoire insuffisante, en utilisant ce type d'implémentation de cache. Cela ne fait qu'accroître les opérations d'E/S de votre application.
Ceci est juste une vue aérienne de la configuration. Il y a beaucoup de configurations pour optimiser vos besoins.

Answer 10

Chronicle Map pourrait avoir un surdébit de moins de 20 octets par entrée (voir a test le prouver). À titre de comparaison, le surcoût de java.util.HashMap varie de 37 à 42 octets avec -XX:+UseCompressedOops à 58-69 octets sans oups compressés (reference). En outre, Chronicle Map stocke les clés et les valeurs hors segment, de sorte qu'il ne stocke pas les en-têtes d'objet, qui ne sont pas pris en compte dans le surdébit de HashMap ci-dessus. Chronicle Map integrates avec Chronicle-Values, une bibliothèque pour la génération d'implémentations flyweight des interfaces, le modèle suggested by Brian Agnew dans une autre réponse.