Estoy buscando una alternativa a la implementación de Java Bitset. Estoy implementando un algoritmo de alto rendimiento y parece que usar un objeto Bitset está matando su rendimiento. ¿Algunas ideas?¿Alternativa a Java Bitset con rendimiento tipo array?
Alguien ha comparado hereboolean[] a BitSet y concluyó con:
BitSetes más eficiente que la memoriaboolean[]a excepción de muy tamaños pequeños. Cadabooleanen la matriz toma un byte. Los números deruntime.freeMemory()son un poco confusos paraBitSet, pero menos.
boolean[]es más eficiente de la CPU a excepción de tamaños muy grandes, donde son casi iguales. Por ejemplo, para el tamaño 1 millónboolean[]es aproximadamente cuatro veces más rápido (por ejemplo, 6ms frente a 27ms), para diez y cien millones son casi iguales.
Si Google, se pueden encontrar algunas implementaciones alternativas, así como JavaEWAH, utilizado por Apache Hive, Apache Spark y Eclipse JGit. Reclama:
El objetivo de la compresión alineada con palabras no es lograr la mejor compresión , sino mejorar el tiempo de procesamiento de las consultas. Por lo tanto, nosotros intentamos ahorrar ciclos de CPU, tal vez a expensas del almacenamiento. Sin embargo, el esquema de EWAH que implementamos siempre es más eficiente en cuanto a almacenamiento que un mapa de bits no comprimido como se implementó en la clase BitSet). A diferencia de algunas alternativas, javaewah no se basa en un esquema patentado.
Look at Javolution FastBitSet: A bitset de alto rendimiento integrado con la infraestructura de recogida como un conjunto de índices y obedeciendo la colección semántica para métodos tales como FastSet.size() (cardinalidad) o FastCollection.equals (java. lang.Object) (el mismo conjunto de índices).
Véase también http://code.google.com/p/guava-libraries/issues/detail?id=724#c3.
Se puede recomendar Javolution one, really performant –
Si realmente debe exprimir el máximo rendimiento de esta cosa, y si la memoria no importa, puede intentar almacenar cada una de sus banderas en un número entero cuyo tamaño de bit es igual a la anchura del bus de datos de tu CPU.
Probablemente esté en una CPU de bus de datos de 64 bits, intente con enteros largos.
¿Por qué no utilizar ints que tienen solo 32 bits de longitud? – rreyes1979
Porque si la alineación cuenta con su arquitectura, entonces quiere ir con el tamaño exacto del bus de datos, ni más ni menos. Y las arquitecturas modernas suelen tener buses de direcciones de 64 bits, no de 32 bits. No estoy diciendo que esto necesariamente funcione, así que asegúrese de compararlo. Depende de cómo su CPU accede a su memoria. –
Mientras busca una respuesta para mi pregunta single byte comparison vs multiple boolean comparison, encontré OpenBitSet
Afirman ser más rápido que Java BitSet y acceso directo a la matriz de palabras que almacenan los bits.
Definitivamente voy a intentar eso. A ver si también resuelve tu propósito.
Hay una serie de alternativas comprimidas a la clase BitSet. EWAH ya fue mencionado (https://github.com/lemire/javaewah).Las adiciones más recientes incluyen Roaring bitmaps (https://github.com/RoaringBitmap/RoaringBitmap) que son utilizados por Apache Lucene, Apache Spark, Elastic Search, etc.
¿Podría darnos más detalles sobre qué operaciones de 'BitSet' parecen * matar el rendimiento *? Un breve fragmento de código que haya perfilado para mostrar su lentitud sería ideal. – dasblinkenlight
Su pregunta debería ser más bien "¿por qué este bitsets está matando mi rendimiento?" - y note que ya le doy un poco de crédito al no sugerir que debería ser "¿qué está matando mi rendimiento aquí?" –
Bueno, una "alternativa" podría estar haciendo operaciones de bits en primitivas (largo, int, etc.) usted mismo. Sin embargo, como ya se dijo, debe detallar sus objetivos y el problema de rendimiento exacto. – Thomas