Alternative à Java Bitset avec la matrice de performance?

Je suis à la recherche d'une alternative à Java Bitset mise en œuvre. Je me suis mise en œuvre d'une haute performance de l'algorithme et semble à l'aide d'un Bitset objet est en train de tuer ses performances. Des idées?

  • Pourriez-vous nous donner plus de détails sur les opérations de BitSet semblent tuer la performance? Un court extrait de code que vous profilé de manière à montrer sa lenteur serait l'idéal.
  • Votre question devrait plutôt être: "pourquoi est-ce bitset tuer de mes performances?" --et vous remarquerez que je suis déjà en train de vous un peu de crédit en ne suggérant qu'il devrait être "ce qui est en train de tuer mes performances ici?"
  • Ainsi, une "alternative" peut-être quelque peu opérations sur les primitives (long, int, etc.) vous-même. Cependant, comme déjà indiqué devrait donner des détails sur vos objectifs et de la performance exacte du problème.
  • Je considère l'ensemble du problème et d'essayer de supprimer la nécessité de créer un BitSet à tous. Pour ce faire j'aurais besoin d'une plus vaste de comprendre le problème que vous essayez de résoudre.
InformationsquelleAutor rreyes1979 | 2012-01-10
  1. 10

    Quelqu'un ici a comparé boolean[] à BitSet et a conclu avec:

    BitSet est plus efficace en terme de mémoire que boolean[], sauf pour de très
    les petites tailles. Chaque boolean dans le tableau prend un octet. Les chiffres
    de runtime.freeMemory() sont un peu confus pour BitSet, mais moins.

    boolean[] est CPU plus efficace, sauf pour les très grandes tailles, où
    ils sont sur le même. E. g., pour la taille 1 million de boolean[] est sur
    quatre fois plus rapide (par exemple, 6ms vs 27 ms est observée), pendant dix et de cent millions de
    ils sont sur le même.

    Si vous Google, vous pouvez trouver quelques-uns des implémentations alternatives, comme JavaEWAH, utilisé par Apache Hive, Apache Spark et Eclipse JGit. Il affirme:

    Le but de mot aligné à la compression est de ne pas atteindre le meilleur
    pour la compression, mais plutôt à améliorer le traitement des requêtes temps. Par conséquent, nous
    essayez d'économiser des cycles CPU, peut-être au détriment de stockage. Cependant, l'
    EWAH schéma nous avons mis en œuvre est toujours plus efficace de stockage sage que
    non compressé image bitmap en tant que mis en œuvre dans la classe BitSet). Contrairement à
    certaines solutions de rechange, javaewah ne repose pas sur un schéma breveté.

    InformationsquelleAutor Behrang
  2. 5

    Lors de la recherche d'une réponse pour ma question seul octet comparaison vs plusieurs boolean comparaison, j'ai trouvé OpenBitSet

    Ils prétendent être plus rapide que Java BitSet et un accès direct à l'ensemble des mots de stocker les bits.

    Je suis définitivement vais essayer ça. Voir si il résoudre votre but.

    InformationsquelleAutor Amit Kumar Gupta
  3. 5

    Regarder Javolution FastBitSet :
    Une haute performance bitset intégré au cadre de collecte comme un ensemble d'indices et d'obéir à la collection sémantique pour des méthodes telles que le réglage rapide.size() (cardinalité) ou FastCollection.equals(java.lang.Objet) (même ensemble d'indices).

    Voir aussi http://code.google.com/p/guava-libraries/issues/detail?id=724#c3.

    • Peut recommander Javolution un, vraiment performant
    InformationsquelleAutor Vadzim
  4. 4

    Si vous vraiment doit serrer le maximum de performance de cette chose, et si la mémoire n'est pas grave, vous pouvez essayer de stockage de chacun de vos drapeaux en un entier dont la taille en bits est égal à la largeur du bus de données de votre CPU.

    Vous êtes probablement sur une version 64 bits du bus de données de la CPU, donc essayez d'entiers longs.

    • Pourquoi ne pas utiliser les services de renseignements qui ne sont qu'à une longueur de 32 bits?
    • Parce que si l'alignement compte sur votre architecture, vous voulez aller avec la taille exacte du bus de données, pas plus, pas moins. Et architectures modernes ont généralement 64 bits de l'adresse de bus, pas de 32 bits. Je ne dis pas que ce sera forcément le travail, assurez-vous donc à l'indice de référence. Cela dépend de votre PROCESSEUR accède à votre mémoire.
    InformationsquelleAutor Mike Nakis
  5. 4

    Il y a un certain nombre de comprimé de solutions de rechange à la classe BitSet. EWAH a déjà été mentionné (https://github.com/lemire/javaewah). Plus récents ajouts comprennent Rugissant bitmaps (https://github.com/RoaringBitmap/RoaringBitmap) qui sont utilisés par Apache Lucene, Apache Spark, Elastic Search, et ainsi de suite.

    InformationsquelleAutor Daniel Lemire