Comment dois-je mapper les clés de chaîne aux valeurs de Java de manière efficace en termes de mémoire?

Je cherche un moyen de stocker un mappage ssortingng-> int. Une HashMap est évidemment la solution la plus évidente, mais comme ma mémoire est limitée et que je dois stocker 2 millions de paires, des clés de 7 caractères, j’ai besoin de quelque chose de efficace en mémoire, la vitesse de récupération est un paramètre secondaire.

Actuellement, je vais dans le sens de:

List<Tuple> list = new ArrayList<Tuple>(); list.add(...); // load from file Collections.sort(list); 

et ensuite pour la récupération:

 Collections.binarySearch(list, key); // log(n), acceptable 

Dois-je peut-être opter pour un arbre personnalisé (chaque nœud un seul caractère, chaque feuille avec un résultat), ou existe-t-il une collection existante qui convient parfaitement? Les chaînes sont pratiquement séquentielles (les codes postaux du Royaume-Uni, ils ne diffèrent pas beaucoup), alors je m’attends à de belles économies de mémoire ici.

    Edit : Je viens de voir que vous avez mentionné que la chaîne était des codes postaux britanniques alors je suis assez sûr que vous ne pourriez pas vous tromper en utilisant un Trove TLongIntHashMap (btw Trove est une petite bibliothèque et il est très facile à utiliser).

    Edit 2 : Beaucoup de gens semblent trouver cette réponse intéressante, alors j’y ajoute des informations.

    L’objective ici est d’utiliser une carte contenant des clés / valeurs d’une manière efficace sur la mémoire afin de commencer par rechercher des collections efficaces en termes de mémoire.

    La question SO suivante est liée (mais loin d’être identique à celle-ci).

    Quelle est la bibliothèque Java Collections la plus efficace?

    Jon Skeet mentionne que Trove est “juste une bibliothèque de collections à partir de types primitifs” et que, en effet, elle n’ajoute pas beaucoup de fonctionnalités. Nous pouvons également voir quelques benchmarks (par le.duckman ) sur la mémoire et la vitesse de Trove par rapport aux collections par défaut. Voici un extrait:

      100000 put operations 100000 contains operations java collections 1938 ms 203 ms trove 234 ms 125 ms pcj 516 ms 94 ms 

    Et il y a aussi un exemple montrant combien de mémoire peut être enregistrée en utilisant Trove au lieu d’un Java HashMap standard :

     java collections oscillates between 6644536 and 7168840 bytes trove 1853296 bytes pcj 1866112 bytes 

    Donc, même si les repères doivent toujours être pris avec un grain de sel, il est évident que Trove économisera non seulement de la mémoire mais sera toujours beaucoup plus rapide.

    Notre objective est donc désormais d’utiliser Trove (vu qu’en plaçant des millions et des millions d’entrées dans un HashMap classique , votre application commence à ne plus répondre).

    Vous avez mentionné 2 millions de paires, 7 clés longues et un mapping Ssortingng / int.

    2 millions, ce n’est vraiment pas grand chose, mais vous sentirez toujours la surcharge “Object” et la constante (dé) boxe des primitives à Integer dans un HashMap classique {Ssortingng, Integer}, ce qui explique pourquoi Trove a beaucoup de sens ici.

    Cependant, je vous signale que si vous contrôlez les “7 caractères”, vous pourriez aller encore plus loin: si vous utilisez uniquement des caractères ASCII ou ISO-8859-1, vos 7 caractères pourraient tenir longtemps ( *). Dans ce cas, vous pouvez éviter la création d’objects et représenter vos 7 personnages sur une longue durée. Vous utiliseriez alors une Trove TLongIntHashMap et contourneriez complètement la surcharge “Object Java”.

    Vous avez indiqué spécifiquement que vos clés étaient de 7 caractères et commentées comme des codes postaux britanniques: je mapperais chaque code postal sur une grande longueur et économiserais énormément de mémoire en ajustant des millions de paires de clés / valeurs à l’aide de Trove.

    L’avantage de Trove est qu’il ne fait pas de boxing / unboxing constant d’objects / primitives: Trove fonctionne dans de nombreux cas directement avec les primitives et les primitives.

    (*) disons que vous n’avez pas plus de 256 points de code / caractères au maximum, puis il s’adapte sur 7 * 8 == 56 bits, ce qui est assez petit pour tenir dans un long.

    Exemple de méthode pour coder les clés Ssortingng en long (en supposant que les caractères ASCII, un octet par caractère pour simplifier – 7 bits suffiraient):

     long encode(final Ssortingng key) { final int length = key.length(); if (length > 8) { throw new IndexOutOfBoundsException( "key is longer than 8 characters"); } long result = 0; for (int i = 0; i < length; i++) { result += ((long) ((byte) key.charAt(i))) << i * 8; } return result; } 

    Utilisez la bibliothèque Trove.

    La bibliothèque Trove a optimisé les classes HashMap et HashSet pour les primitives. Dans ce cas, TObjectIntHashMap l’object paramétré ( Ssortingng ) à une primitive int .

    Tout d’abord, avez-vous mesuré que LinkedList est en effet plus efficace en HashMap mémoire qu’un HashMap , ou comment en êtes-vous arrivé à cette conclusion? Deuxièmement, le temps d’access d’un élément au LinkedList est O(n) , vous ne pouvez donc pas effectuer de recherche binary efficace. Si vous voulez faire une telle approche, vous devriez utiliser une ArrayList , qui devrait vous donner le compromis entre performance et espace. Cependant, encore une fois, je doute qu’un HashMap , HashTable ou – en particulier – un TreeMap consumnt beaucoup plus de mémoire, mais les deux premiers fourniraient un access constant et un logarithmique à la carte arborescente et fourniraient une interface plus agréable. Je voudrais essayer de faire des mesures, quelle est la différence de consommation de mémoire.

    MISE À JOUR : Étant donné, comme Adamski l’a fait remarquer, que les Ssortingng elles-mêmes, et non la structure de données dans laquelle elles sont stockées, consumront le plus de mémoire, il pourrait être judicieux d’examiner des structures de données spécifiques aux chaînes. (en particulier les essais de pasortingcia ), ce qui pourrait réduire l’espace de stockage nécessaire pour les chaînes.

    Ce que vous recherchez, c’est une formule succincte – un sorting qui stocke ses données dans le moins d’espace théorique possible.

    Malheureusement, aucune bibliothèque de classes succinctes n’est actuellement disponible pour Java. Un de mes prochains projets (dans quelques semaines) consiste à en écrire un pour Java (et d’autres langages) .

    En attendant, si cela ne vous dérange pas JNI , il existe plusieurs bonnes bibliothèques natives succinctes-sortinge auxquelles vous pouvez vous référer.

    Avez-vous regardé les essais ? Je ne les ai pas utilisés mais ils peuvent correspondre à ce que vous faites.

    Une arborescence personnalisée aurait la même complexité de O(log n) , ne vous embêtez pas. Votre solution est valable, mais j’irais avec un ArrayList au lieu de LinkedList car la liste liée alloue un object supplémentaire par valeur stockée, ce qui équivaut à beaucoup d’objects dans votre cas.

    Comme Erick écrit à l’aide de la bibliothèque Trove, c’est un bon sharepoint départ, car vous économisez de l’espace en stockant les primitives int plutôt que les Integer s.

    Cependant, vous devez encore stocker 2 millions d’instances de chaîne. Étant donné que ce sont des clés sur la carte, les interner ne leur offrira aucun avantage. La prochaine chose que je prendrai en compte sera de savoir si certaines chaînes de caractères peuvent être exploitées. Par exemple:

    • Si les Ssortingng représentent des phrases de mots communs, vous pouvez transformer la chaîne en une classe Sentence et interner les mots individuels.
    • Si les chaînes ne contiennent qu’un sous-ensemble de caractères Unicode (par exemple, uniquement des lettres AZ ou des lettres + chiffres), vous pouvez utiliser un schéma de codage plus compact que Unicode Java.
    • Vous pouvez envisager de transformer chaque chaîne en un tableau d’octets codé en UTF-8 et de l’ MySsortingng dans la classe: MySsortingng . Évidemment, le compromis est le temps supplémentaire passé à effectuer des recherches.
    • Vous pouvez écrire la carte dans un fichier, puis mapper une partie ou la totalité du fichier.
    • Vous pouvez envisager des bibliothèques telles que Berkeley DB qui vous permettent de définir des cartes persistantes et de mettre en cache une partie de la carte en mémoire. Cela offre une approche évolutive.

    peut-être que vous pouvez aller avec un RadixTree ?

    Utilisez java.util.TreeMap au lieu de java.util.HashMap . Il utilise un arbre de recherche binary rouge noir et n’utilise pas plus de mémoire que ce qui est requirejs pour contenir des notes contenant les éléments de la carte. Pas de seaux supplémentaires, contrairement à HashMap ou Hashtable.

    Je pense que la solution consiste à sortir un peu de Java. Si vous avez autant de valeurs, vous devez utiliser une firebase database. Si vous n’avez pas envie d’installer Oracle, SQLite est rapide et facile. De cette façon, les données dont vous n’avez pas besoin immédiatement sont stockées sur le disque et toute la mise en cache / le stockage est effectuée pour vous. Configurer un DB avec une table et deux colonnes ne prendra pas beaucoup de temps.

    J’envisagerais d’utiliser un cache car ceux-ci ont souvent la capacité de débordement sur disque .

    Vous pouvez créer une classe de clés correspondant à vos besoins. Peut-être comme ça:

     public class MyKey implements Comparable { char[7] keyValue; public MyKey(Ssortingng keyValue) { ... load this.keyValue from the Ssortingng keyValue. } public int compareTo(MyKey rhs) { ... blah } public boolean equals(Object rhs) { ... blah } public int hashCode() { ... blah } } 

    essaye celui-là

     OptimizedHashMap myMap = new OptimizedHashMap(); for(int i = 0; i < 2000000; i++) { myMap.put("iiiiii" + i, new int[]{i}); } System.out.println(myMap.containsValue(new int[]{3})); System.out.println(myMap.get("iiiiii" + 1)); 

     public class OptimizedHashMap extends HashMap { public boolean containsValue(Object value) { if(value != null) { Class aClass = value.getClass(); if(aClass.isArray()) { Collection values = this.values(); for(Object val : values) { int[] newval = (int[]) val; int[] newvalue = (int[]) value; if(newval[0] == newvalue[0]) { return true; } } } } return false; } 

    En fait, HashMap et List sont trop généraux pour une tâche spécifique telle que la recherche de int par code postal. Vous devez utiliser les connaissances acquises pour savoir quelles données sont utilisées. L’une des options consiste à utiliser un arbre de préfixe avec des feuilles qui stocke la valeur int. En outre, il pourrait être élagué si (à mon avis) beaucoup de codes avec les mêmes préfixes correspondent au même entier.

    La recherche de l’int par code postal sera linéaire dans cet arbre et ne grossira pas si le nombre de codes est augmenté, comparé à O (log (N)) en cas de recherche binary.

    Comme vous avez l’intention d’utiliser le hachage, vous pouvez essayer les conversions numériques des chaînes en fonction des valeurs ASCII. l’idée la plus simple sera

      int sum=0; for(int i=0;i 

    hash "sum" en utilisant des fonctions de hachage bien définies. Vous utiliseriez une fonction de hachage basée sur les modèles d'entrée attendus. par exemple si vous utilisez la méthode de division

      public int hasher(int sum){ return sum%(a prime number); } 

    La sélection d'un nombre premier qui n'est pas proche d'une puissance exacte de deux améliore les performances et donne une meilleure dissortingbution des clés hachée de manière uniforme.

    une autre méthode consiste à peser les caractères en fonction de leur position respective.

    ex: si vous utilisez la méthode ci-dessus, "abc" et "cab" seront tous deux hachés au même endroit. mais si vous avez besoin de les stocker dans deux emplacements distincts, atsortingbuez des pondérations aux emplacements comme nous utilisons les systèmes de numération.

      int sum=0; int weight=1; for(int i=0;i 

    Comme votre échantillon est assez volumineux, vous éviterez les collisions par un mécanisme de chaînage plutôt que d'utiliser une séquence de sondes. Après tout, la méthode que vous choisiriez dépend totalement de la nature de votre application.

    Le problème est la surcharge des objects, mais en utilisant certaines astuces, vous pouvez essayer d’implémenter votre propre hashset. Quelque chose comme ça . Comme d’autres, les chaînes de caractères ont une surcharge importante, vous devez donc les compresser. Essayez également de ne pas utiliser trop de tableaux (listes) dans la table de hachage (si vous en faites un type de hachage), car ils sont également des objects et ont également une surcharge. Mieux encore, ouvrez l’adressable hashtable.