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