Альтернатива Java Bitset с производительностью, подобной массиву?

Question

Я ищу альтернативу реализации Java Bitset. Я реализую высокопроизводительный алгоритм и похоже, что использование объекта Bitset снижает его производительность. Есть идеи?

Answer 1

Кто-то здесь сравнил boolean[] с BitSet и пришел к выводу:

BitSet более эффективно использует память, чем boolean[], за исключением очень маленьких размеров.Каждый boolean в массиве занимает байт.Числа от runtime.freeMemory() немного запутаны для BitSet, но меньше.

boolean[] более эффективен с точки зрения использования процессора, за исключением очень больших размеров, где они примерно одинаковы.Например, для размера 1 миллион boolean[] примерно в четыре раза быстрее (например, 6 мс против 27 мс), для десяти и ста миллионов они примерно одинаковы.

Если вы Google, вы можете найти какую-то альтернативуреализации, например, JavaEWAH , используемые Apache Hive , Apache Spark и Eclipse JGit .Он утверждает:

Целью сжатия с выравниванием по словам является не достижение наилучшего сжатия, а скорее улучшение времени обработки запросов.Следовательно, мы пытаемся сохранить циклы процессора, возможно, за счет хранения.Однако реализованная нами схема EWAH всегда более эффективна с точки зрения хранения, чем несжатый битовый образ, реализованный в классе BitSet).В отличие от некоторых альтернатив, javaewah не опирается на запатентованную схему.

Answer 2

При поиске ответа на мой вопрос Сравнение однобайтовых и множественных логических сравнений , я обнаружил OpenBitSet

Они утверждают, что они быстрее, чем Java BitSet и прямой доступк массиву слов, хранящему биты.

Я определенно собираюсь попробовать это.Посмотри, решит ли это и твою цель.

Answer 3

Посмотрите на Javolution FastBitSet : Высокопроизводительный набор битов, интегрированный со структурой сбора в виде набора индексов и подчиняющийся семантике сбора для таких методов, как FastSet.size () (cardinality) или FastCollection.equals (java.lang.Object) (тот же набор индексов)

См. Также http://code.google.com/p/guava-libraries/issues/detail?id=724#c3.

Answer 4

Существует несколько сжатых альтернатив классу BitSet. EWAH уже упоминался (https://github.com/lemire/javaewah). Более новые добавления включают Ревущие растровые изображения (https://github.com/RoaringBitmap/RoaringBitmap), которые используются Apache Lucene, Apache Spark, Elastic Search и т.

Answer 5

Если вы действительно должны выжать максимальную производительность из этой вещи, и если память не имеет значения, вы можете попытаться сохранить каждый из ваших флагов в целом числе, размер бит которого равен ширине шина данных вашего процессора.

Возможно, вы используете 64-битный процессор шины данных, поэтому попробуйте длинные целые числа.