Implémentations optimisées de java.util.Map et java.util.Set?

Je suis en train d'écrire une application où la mémoire, et dans une moindre mesure de la vitesse, sont essentiels. J'ai trouvé de profilage et que je passe beaucoup de temps dans la Carte et de l'Ensemble des opérations. Alors que je regarde façons d'appeler ces méthodes moins, je me demandais si quelqu'un y a écrit, ou venir à travers, des implémentations d'améliorer significativement le temps d'accès ou de surcharge de la mémoire? ou au moins, qui peuvent améliorer ces choses compte tenu de certaines hypothèses?

En regardant le JDK source, je ne peux pas croire qu'il ne peut pas être effectuée plus rapidement ou plus maigre.

Je suis conscient des Communes Collections, mais je ne crois pas qu'elle ait une mise en œuvre dont l'objectif est d'être plus rapide ou plus maigre. De même pour Google Collections.

Mise à jour: Devrait avoir noté que je n'ai pas besoin de thread.

source d'informationauteur Sean Owen

  1. 11

    Normalement, ces méthodes sont assez rapide.
    Il ya un couple de choses que vous devez vérifier: des codes de hachage mis en œuvre? Sont-ils suffisamment uniforme? Autrement vous aurez des ordures de la performance.

    http://trove4j.sourceforge.net/ <-- c'est un peu plus rapide et permet d'économiser de la mémoire. J'ai sauvé quelques ms sur 50 000 mises à jour

    Êtes-vous sûr que vous êtes à l'aide de cartes/jeux correctement? c'est à dire de ne pas essayer de parcourir toutes les valeurs ou quelque chose de similaire. Aussi, par exemple, ne contient, puis supprimer. Cochez simplement la supprimer.

    Également vérifier si vous êtes en utilisant le Double vs double. J'ai remarqué quelques ms améliorations des performances sur des dizaines de milliers de chèques.

    Avez-vous également mis en place la capacité initiale correctement/correctement?

  2. 7

    Avez-vous regardé Trove4J ? À partir du site web:

    Trésor vise à fournir un service rapide, léger implémentations de java.util.Les Collections de l'API.

    Repères fournis ici.

  3. 6

    Ici sont celles que je connais, en plus de Google et les Communes Collections:

    Bien sûr, vous pouvez toujours mettre en œuvre vos propres structures de données qui sont optimisés pour votre cas d'utilisation. Pour être en mesure de mieux, nous aurions besoin de savoir que vous les modèles d'accès et de quel type de données que vous stockez dans les collections.

  4. 4

    Essayez d'améliorer les performances de votre equals et hashCode méthodes, ce qui pourrait aider à accélérer le conteneur standard de l'utilisation de vos objets.

  5. 2

    Vous pouvez étendre AbstractMap et/ou AbstractSet comme un point de départ. Je l'ai fait il y a pas longtemps pour mettre en œuvre un binaire trie en fonction de la carte (la clé a été un entier, et chaque "niveau" sur l'arbre était un peu de la position. gauche de l'enfant de 0 et de droit de l'enfant était de 1). Cela a bien fonctionné pour nous, parce que la clé a été EUI-64 identifiants, et pour nous la plupart du temps dans le top 5 octets ont été va être le même.

    De mettre en œuvre un AbstractMap, vous devez à tout le moins de mettre en œuvre la entrySet() la méthode, pour retourner un jeu de Carte.Entrée, dont chacun est une paire clé/valeur.

    À mettre en œuvre un ensemble, vous étendez AbstractSet et de l'approvisionnement des implémentations de taille() et iterator().

    C'est à tout le moins, cependant. Vous souhaitez également mettre en œuvre get et put, car la valeur par défaut de la carte est inmodifiable, et l'implémentation par défaut de l'obtenir parcourt la entrySet la recherche d'un match.

  7. 1

    Il y a au moins une mise en œuvre de commons-collections spécialement construit pour la vitesse: Flat3Map c'est assez spécifique que ça va être très rapide aussi longtemps qu'il n'y a plus de 3 éléments.

    Je soupçonne que vous pouvez obtenir plus de kilométrage en suivant @thaggie les conseils d'ajouter de l'allure à l'est égal à/hashcode de la méthode des moments.

  8. 1

    Vous avez dit que vous profilé certaines classes, mais avez-vous fait des horaires à vérifier leur vitesse? Je ne suis pas sûr de la façon dont vous devriez vérifier leur utilisation de la mémoire. Il me semble qu'il serait bien d'avoir des chiffres précis à portée de main lorsque vous êtes en comparant les différentes implémentations.

  9. 1

    Il y a quelques notes ici et des liens vers plusieurs de remplacement de la structure des données des bibliothèques: http://www.leepoint.net/notes-java/data/collections/ds-alternatives.html

    Je vais également jeter dans une voix forte pour fastutil. (mentionné dans une autre réponse, et de la page) Il a plus de différentes structures de données que vous pouvez secouer un bâton à, et des versions optimisées pour les types primitifs comme des clés ou des valeurs. (L'inconvénient est que le fichier jar est énorme, mais vous pouvez probablement couper juste ce dont vous avez besoin)

  10. 1

    Je suis passé par quelque chose comme cela, il y a quelques années, de très grandes Cartes et des Jeux, ainsi que de très nombreux d'entre eux. La valeur par défaut implémentations Java consommé trop d'espace. En fin de compte, j'ai roulé ma propre, mais seulement après que j'ai passé en revue les modes d'utilisation que mon code requis. Par exemple, j'avais connu un grand ensemble d'objets qui ont été créés dès le début, et certaines Cartes étaient rares, tandis que d'autres ont été denses. D'autres structures ont augmenté de façon monotone (pas de suppressions) alors que dans d'autres endroits, il a été plus rapide d'utiliser une "collection" et de faire de l'occasionnel mais inoffensif travail supplémentaire de traitement de dupliquer les éléments qu'il a été de passer du temps et de l'espace pour éviter les doublons. La plupart des implémentations j'ai utilisé ont été tableau adossés à et exploité le fait que mon hashcodes ont été successivement affecté et donc pour les cartes denses, une recherche a été juste un tableau.

    Emporter messages:

    1. regardez votre algorithme,
    2. envisager de multiples implémentations, et
    3. rappelez-vous que la plupart des bibliothèques sont de traiteur pour un usage général (par exemple insérer et supprimer, une gamme de tailles, ni éparses, ni dense, etc) donc ils vont avoir des frais généraux que vous pouvez probablement éviter.

    Oh, et écrire des tests unitaires...

  11. 1

    De temps en temps quand je dois voir la Carte et Définir les opérations à l'aide d'un haut pourcentage de CPU, il a indiqué que j'ai plus de Carte, et de Définir et de restructuration de mes données a presque éliminé les collections du top 10% de CPU consommateur.

    Voir si vous pouvez éviter les copies des collections, itérer sur les collections et toute autre opération qui résultats dans l'accès à la plupart des éléments de la collection et la création d'objets.

  12. 0

    Ce n'est probablement pas tellement le Map ou Set qui pose problème, mais les objets derrière eux. Selon votre problème, vous voudrez peut-être un plus de la base de données de type schéma, où les "objets" sont stockés comme un tas d'octets plutôt que des Objets Java. Vous pouvez inclure une base de données (comme Apache Derby) ou faire votre propre spécialiste de la chose. Il est très dépendant de ce que vous êtes en train de faire. HashMap n'est pas délibérément en gros et lent...

  13. 0

    Commons Collections a FastArrayListFastHashMap et FastTreeMap mais je ne sais pas ce qu'ils valent...

  14. 0
    • Commons Collections a un id de la carte, ce qui se compare au travers de ==, ce qui devrait être plus rapide.
      -[Joda Primities][1] comme primitive collections, comme le fait Mine de. J'ai expérimenté avec Mine et a constaté que sa mémoire useage est mieux.
    • J'étais cartographie des collections de nombreux petits objets avec un peu de nombres Entiers. la modification de ces à ints permis de sauver près de la moitié de la mémoire (bien que nécessitant quelques messier code de l'application pour compenser).
    • Il me semble raisonnable que triées, les arbres doivent consommer moins de mémoire que hashmaps parce qu'ils n'ont pas besoin du facteur de charge (bien que, si quelqu'un peut confirmer ou a une raison pourquoi c'est réellement stupide veuillez poster dans les commentaires).
  15. 0

    La version de la JVM utilisez-vous?

    Si vous n'êtes pas sur 6 (bien que je soupçonne que vous êtes), puis un commutateur à 6 peuvent aider.

    Si c'est un serveur d'application et est en cours d'exécution sur windows essayez d'utiliser de serveur à utiliser le bon hotspot de la mise en œuvre.

  16. 0

    J'utilise le package suivant (koloboke) pour en faire un int-int hashmap, car il prend en charge promitive type et la stocke deux int dans une variable de type long, c'est cool pour moi. koloboke