Я ищу альтернативу реализации Java Bitset. Я реализую алгоритм высокой производительности и, похоже, использует объект Bitset, который убивает его производительность. Есть идеи?Альтернатива Java Bitset с массивом, как производительность?
Кто here сравнил boolean[] к BitSet и заключил с:
BitSetбольше памяти эффективнее, чемboolean[]для самых малых размеров, за исключением. Каждыйbooleanв массиве принимает байт. Номера отruntime.freeMemory()немного запутаны дляBitSet, но меньше.
boolean[]более эффективен с точки зрения эффективности процессора, за исключением очень больших размеров, где они примерно равны. Например, для размера 1 млн.boolean[]составляет примерно в четыре раза быстрее (например, 6 мс против 27 мс), для десяти и сто миллионов они примерно четные.
Если вы Google, вы можете найти некоторые альтернативные реализации, а также, как JavaEWAH, используемый Apache Hive, Apache Spark и Eclipse JGit. Он утверждает:
Цель сжатия с выравниванием по слову - не добиться максимальной компрессии , а улучшить время обработки запроса. Следовательно, попытайтесь сохранить циклы процессора, возможно, за счет хранения. Однако реализованная нами схема EWAH всегда более эффективна по хранению, чем несжатое растровое изображение, реализованное в классе BitSet). В отличие от некоторые альтернативы, javaewah не полагается на запатентованную схему.
Посмотрите на Javolution FastBitSet: BitSet высокоэффективных интегрирован с рамками сбора в виде набора индексов и повинуясь сбором семантических методов, таких как FastSet.size() (мощность) или FastCollection.equals (Java. lang.Object) (тот же набор индексов).
См. Также http://code.google.com/p/guava-libraries/issues/detail?id=724#c3.
Может порекомендовать Javolution один, действительно эффективный –
Если вы действительно должны сжать максимальную производительность из этой вещи, и если память не имеет значения, вы можете попробовать сохранить каждый из своих флагов в целочисленном размере, размер бита которого равен ширине шины данных вашего процессора.
Возможно, вы находитесь на 64-битном ЦП шины данных, поэтому попробуйте длинные целые числа.
Почему бы не использовать ints длиной всего 32 бита? – rreyes1979
Потому что, если выравнивание рассчитывается на вашей архитектуре, то вы хотите пойти с точным размером шины данных, не более, не меньше. А современные архитектуры обычно имеют 64-битные адресные шины, а не 32-битные. Я не говорю, что это обязательно сработает, поэтому обязательно сравните его. Это зависит от того, как ваш процессор обращается к вашей памяти. –
При поиске ответа на мой вопрос single byte comparison vs multiple boolean comparison, я нашел OpenBitSet
Они утверждают, что быстрее, чем Java BitSet и прямой доступ к массиву слов, хранящих биты.
Я определенно собираюсь попробовать это. Посмотрите, не решит ли ваша цель.
Существует ряд сжатых альтернатив классу BitSet. EWAH уже упоминалось (https://github.com/lemire/javaewah).Более свежие дополнения включают реверсивные растровые изображения (https://github.com/RoaringBitmap/RoaringBitmap), которые используются Apache Lucene, Apache Spark, Elastic Search и т. Д.
Не могли бы вы дать нам более подробную информацию о том, какие операции «BitSet» появляются, чтобы убить производительность *? Короткий фрагмент кода, который вы профилировали, чтобы показать его медлительность, был бы идеальным. – dasblinkenlight
Ваш вопрос скорее должен быть «почему этот битбит убивает мою работу?» - и обратите внимание, что я уже даю вам некоторую оценку, не предлагая, чтобы это было «что убивает мою работу здесь?» –
Ну, «альтернативный» может выполнять бит-операции на примитивах (long, int и т. Д.) Самостоятельно. Однако, как уже было сказано, вы должны уточнить свои цели и точную производительность. – Thomas