Comment mapper les clés de chaîne sur les valeurs en Java de manière à optimiser la mémoire?

Question

Je suis à la recherche d'un moyen de stocker une chaîne de caractères->int cartographie. Une table de hachage est, bien sûr, une solution évidente, mais comme je suis limitée par la mémoire et la nécessité de stocker 2 millions de paires, 7 caractères les touches, j'ai besoin de quelque chose qui est efficace en terme de mémoire, la vitesse de récupération est un paramètre secondaire.

Actuellement, je vais le long de la ligne de:

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

et puis pour la récupération:

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

Je devrais peut-être aller pour une arborescence personnalisée (chaque nœud d'un seul caractère, chaque feuille avec un résultat), ou est-il une collection existante qui correspond à ce bien? Les cordes sont pratiquement séquentielle (royaume-UNI, les codes postaux, ils ne diffèrent pas beaucoup), donc je m'attends à nice économies de mémoire ici.

Answer 1

Edit: je viens de voir que vous avez mentionné la Chaîne BRITANNIQUE étaient codes postaux donc je suis assez confiant, vous ne pourriez pas obtenir de très mauvais à l'aide d'un Trésor TLongIntHashMap (btw Trésor est une petite bibliothèque et il est très facile à utiliser).

Edit 2: Beaucoup de gens semblent trouver cette réponse intéressante donc, je vais ajouter quelques informations.

Le but ici est d'utiliser une carte contenant les clés/valeurs dans une mémoire efficace donc nous allons commencer par la recherche de l'efficacité de mémoire de collections.

La suite DONC, la question est liée (mais loin d'être identique à celle-ci).

Quel est le plus efficace Java Collections de la bibliothèque?

Jon Skeet mentionne que la Mine est "juste une bibliothèque de collections de types primitifs" [sic], et que, en effet, il n'ajoute pas beaucoup de fonctionnalités. Nous pouvons également voir quelques repères (par l'.duckman) sur la mémoire et la vitesse de la Mine par rapport à la valeur par défaut des Collections. 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 comment la quantité de mémoire peut être sauvé par l'utilisation de Mine au lieu de Java ordinaire HashMap:

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 assez évident que Trove permettra d'économiser non seulement la mémoire mais ce sera toujours beaucoup plus rapide.

Notre objectif devient maintenant utiliser Trésor (vu qu'en mettant des millions et des millions d'entrées dans une table de hachage, votre application commence à se sentir ne répond pas).

Vous avez mentionné 2 millions de paires, 7 caractères touches et d'un String/int cartographie.

2 millions est vraiment pas beaucoup, mais vous aurez toujours l'impression que le "Objet" de la surcharge et de la constante (de l'onu)de boxe de primitives de type Entier dans une table de hachage{String,Integer}, qui est pourquoi Trove fait beaucoup de sens ici.

Cependant, je ferais remarquer que si vous avez le contrôle sur le "7 caractères", vous pourrait aller encore plus loin: si vous utilisez seulement dire ASCII ou ISO-8859-1 caractères, votre 7 personnages tiennent dans un long (*). Dans ce cas, vous pouvez esquiver complètement création d'objets et de représenter vos 7 caractères de long. Vous devez ensuite utiliser un Trésor TLongIntHashMap et de contourner la "Objet Java-dessus de la tête tout à fait.

Vous avez déclaré expressément que vos clés ont été de 7 caractères et commente ensuite ils étaient le royaume-UNI code postal: j'avais une carte pour chaque code postal d'une longue et économiser une grande quantité de mémoire par l'ajustement des millions de clés/valeurs de la paire dans la mémoire à l'aide de Trésors.

L'avantage de la Mine est fondamentalement que c'est pas constants boxing/unboxing des Objets/primitives: Mine de travaux, dans de nombreux cas, directement avec les primitives et les primitives seulement.

(*) dire que vous avez seulement à plus de 256 codepoints/caractères utilisés, alors qu'il s'adapte sur 7*8 == 56 bits, ce qui est assez petit pour tenir dans une longue.

Exemple de méthode pour l'encodage de l' String clés en longs '(en supposant que des caractères ASCII, un octet par caractère de simplification - 7 bits serait suffisant):

long encode(final String 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;
}

Answer 2

Utilisez la bibliothèque Trove.

La bibliothèque Trove a optimisé les classes HashMap et HashSet pour les primitives. Dans ce cas, TObjectIntHashMap<String> mappera l'objet paramétré ( String ) sur une primitive int .

Answer 3

D'abord, avez-vous mesurer qu' LinkedList est en effet plus efficace en terme de mémoire qu'un HashMap, ou comment êtes-vous arrivé à cette conclusion? D'autre part, un LinkedList's le temps d'accès d'un élément est - O(n), de sorte que vous ne pouvez pas faire efficace binaire de recherche sur elle. Si vous voulez faire une telle approche, vous devez utiliser un ArrayList, ce qui devrait vous donner la bête compromis entre la performance et de l'espace. Cependant, encore une fois, je doute qu'un HashMap, HashTable ou - en particulier, TreeMap n'en consomment beaucoup plus de mémoire, mais les deux premiers fournir un accès constant et l'arbre de la carte logarithmique et de fournir une interface plus conviviale qu'une liste normale. Je voudrais essayer de faire quelques mesures, la différence dans la consommation de mémoire est vraiment.

Mise à JOUR: étant Donné, comme Adamski a souligné, que l' Strings eux-mêmes, et non pas la structure des données qu'ils sont stockés en consomment le plus de mémoire, il pourrait être une bonne idée de se pencher sur les structures de données qui sont spécifiques pour les chaînes de caractères, tels que la tente (surtout patricia tente), ce qui pourrait réduire l'espace de stockage nécessaire pour les chaînes de caractères.

Answer 4

Ce que vous cherchez est un succincte-trie - un trie qui stocke ses données dans presque le moins d'espace possible, en théorie.

Malheureusement, il n'y a pas succincte-trie classes des bibliothèques actuellement disponible pour Java. L'un de mes prochains projets (dans quelques semaines) est d'en écrire un pour Java (et autres langues).

En attendant, si vous n'avez pas l'esprit de la JNI, il y a plusieurs bonnes natif succincte-trie les bibliothèques, vous pouvez référencer.

Answer 5

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