Java: разреженный битовый вектор
Есть ли в Java известные библиотеки для разреженных битовых векторов?
(И есть ли рекомендации о том, насколько полезно их использовать по сравнению с java.util.BitSet?)
8 ответов
Библиотека кольтов имеет разреженные матрицы (1D, 2D и 3D). Он также имеет эффективный BitVector, с 1 битом на значение, а не 8 битами как boolean[] делает.
Тем не менее, разреженные матрицы не поддерживают биты напрямую - только удваиваются и объекты. Вы можете обернуть 1D разреженную двойную матрицу, отобразив битовый индекс на длинные индексы (bitIndex>>6) поскольку каждый long содержит 64 бита, преобразуйте полученный double в необработанное значение long и используйте битовую манипуляцию для доступа к битам восстановленного long. Небольшая работа, но далеко не так много, как реализация разреженного вектора самостоятельно. Как только ваша оболочка заработает, вы можете избежать преобразования двойных значений в длинные и реализовать реальную разреженную длинную 1d-матрицу, используя доступный исходный код Colt для двойной одномерной разреженной матрицы в качестве отправной точки.
РЕДАКТИРОВАТЬ: Больше информации. Для векторов / матриц Colt изначально не требуется памяти для хранения, при условии, что все биты (длинные) изначально равны 0. Установка значения, отличного от нуля, потребляет память. Установка значения обратно в 0 продолжает потреблять память, хотя память для нулевых значений периодически восстанавливается.
Если биты действительно разрежены, так что для каждого длинного значения резервирования установлен только один бит, тогда затраты на хранение будут очень низкими, требуя 64 бита на фактический сохраненный бит. Но, как вы упомянули, типичный случай составляет 20-40% разреженных, тогда издержки будут намного ниже, возможно, без потери памяти, если биты сгруппированы в диапазонах, например, биты от 0-100, затем 1000-1100 и 2000-2200 (значения в шестнадцатеричном формате.) В целом, только 1/16 области назначается битам, но кластеризация означает, что биты хранятся без потери места.
TL;DR иди сюда Эффективная реализация Sparse BitSet в Java
Я знаю, что это "старый" вопрос, но, имея тот же вопрос, я наткнулся на этот пост. Хотя ответы хорошие, я в конечном итоге не был удовлетворен. После дальнейших раскопок, я думаю, я наткнулся на "окончательный" ответ на вопрос о редких BitSets в Java.
В этой презентации автор, доктор Брюс Хэддон, обсуждает усилия своих исследователей по созданию высокоэффективного и высокопроизводительного заменителя памяти для стандартного Java BitSet.
Оригинальные ссылки на его презентацию мертвы, но я связался с доктором Хэддоном и сохранил здесь и код, и презентацию:
https://github.com/brettwooldridge/SparseBitSet
Я не могу рекомендовать читать эту презентацию более высоко. Это увлекательное чтение, даже если вы не интересуетесь разреженными битами, это больше касается истинной природы решения проблем...
Слайды: это информатика, разработка программного обеспечения или взлом?
Если это действительно редко (например, загрузка менее 1%), то использование хеш-таблицы, индексированной по индексу битов, вероятно, очень хорошо; просто наличие или отсутствие индекса в таблице - это все, что вам нужно знать, если бит равен единице или нулю соответственно.
Если плотность выше нескольких процентов, вы можете использовать хеш-таблицу, индексированную по индексу битов, деленному на 64, и хранить длинные слова в хеш-таблице, содержащей фактические биты. Бит N устанавливается, если хеш-таблица содержит значение V для int(N/64) и (V>>(N mod 64))&1 - true.
Оба этих ответа предполагают, что вы хотите оптимизировать произвольный доступ к битам. Если вы хотите оптимизировать последовательный (или другой доступ) к битам по индексу, то вам может потребоваться разреженная матричная структура, использующая тот же тип низкоуровневого представления битового вектора в зависимости от ожидаемой плотности. См разреженных матриц
Очень поздно на вечеринку, но у этого вопроса довольно высокий PageRank. Roaring Bitmap съел много таких вариантов использования.
Вы можете попробовать библиотеку JavaEWAH.
https://code.google.com/p/javaewah/
В зависимости от вашей проблемы это может подойти.
(Используется Apache Hive и другими.)
CERN COLT широко используется для вычисления векторов и матриц и имеет разреженные матрицы, но специально не используется для битовых векторов.
http://acs.lbl.gov/software/colt/api/cern/colt/matrix/impl/SparseObjectMatrix1D.html
Хеш-таблица, где простое присутствие или отсутствие ключа что-то говорит вам? Это будет хэш-сет тогда! Я скептически отношусь к производительности набора (даже хэшированного) по сравнению с BitSet. Это действительно зависит от того, является ли скорость или память основным драйвером.