Ensemble contenant peu d'éléments [Résolu]

[LGnord]

Bonjour,

J'ai à manipuler beaucoup d'ensembles (quelques millions) qui ont une petite taille (typiquement 2 ou 3 éléments; quelques centaines dans le pire des cas).

Par habitude, j'ai utilisé un HashSet mais j'ai des problème de mémoire. En effet, sa capacité est initiale est de 16. Dans mon cas, j'en conclut que typiquement 13/14 espaces mémoires sont utilisés mais vide. Et 13*1 000 000, cela fait beaucoup.

Du coup, j'ai envie de diminuer la taille par défaut. Par exemple, je peux prendre la valeur 2. J'ai du mal à évaluer les conséquence de ce choix. Avez-vous du feedback à partager?

Y-a-t-il d'autres choix possibles?

Merci de votre aide.

[Népomucène]

quelques millions ...

Ces quantités sont habituellement plutôt traitées par une base de données.
- Quels sont les éléments de ces ensembles ?
- Quels types de traitements sur les éléments / ensembles ?

[LGnord]

Merci de ton aide.

D'abord mes ensembles contiennent des entiers.

J'ai deux actions sur les ensembles:
- ajouter un élément (au sens d'un ensemble i.e. je ne veux pas de doublon),
- itérer sur tous les éléments.

Concrètement, je représente un automate (faiblement) non déterministe. Je stocke donc des règles du style:
état --- transition ----> ensemble d'états

[Népomucène]

La base de donnée peut répondre à ce problème
(capable de refuser les doublons)
et aussi pour l'itération.

Il y aura un petit travail d'optimisation à prévoir mais bon ...

[LGnord]

Merci pour ton aide.

Je garde l'idée de la base de données sous le coude mais j'aimerai l'éviter. Elle va à contre courant que ce que nous voulons faire.

[Népomucène]

as-tu vu qu'en lançant ton application, tu peux demander à la JVM d'augmenter la mémoire utilisée :

Code :

-Xms32m -Xmx512m

[LGnord]

Oui, je suis déjà au max de ce que mon ordi peut supporter.

[dinobogan]

Les traitements que tu as à effectuer ne sont pas très clair. tu pourrais peut-être imaginer faire un Graphe par toi-même ? Donc plus de HashSet avec les nombreux trous.
Reste à voir si la vérification d'unicité se fait une fois pour toute au démarrage ou pas. Si c'est tout au long de la durée de vie du programme, il faudrait peut-être voir à stocker les données dans une liste maintenue triée avec recherche dichotomique pour savoir si une valeur existe déjà.

[tchize_]

Clairement, si t'as un million de structures généralement petites, oublie les structures complexe comme les objet. Pour chaque entier sotcké dans le set tu va créer un wrapper (Integer), tu va devoir avoir la structure du set en lui même et son espace de stockage. Un HashSet, en plus, utiliser un table de hashage et des listes chainée. Un hashset occupe donc beaucoup plus d'espace en mémoire qu'un simple tableau. Quand on regarde sur le net, on estime qu'un "grand tableau" occupe à peu près la place des données qu'il contient. Par contre, un hashset, pour y stocker des primitif, on en arrive à un facteur 20.
Bref, un hashset avec beaucoup d'entier occupe environ 20x plus de mémoire qu'un tableau de la même quantité d'entiers.

[LGnord]

Bref, un hashset avec beaucoup d'entier occupe environ 20x plus de mémoire qu'un tableau de la même quantité d'entiers.

C'est une information qui m'est super utile.

Merci pour ton aide.

[LGnord]

Je marque le sujet comme résolu car l'idée de tchize m'a permis de faire un très grand pas en avant.

Néanmoins, si quelqu'un a une autre idée, je continue ma veille.