Java: разреженный бит-вектор

Ответ 1

библиотека жеребца имеет разреженные матрицы (1D, 2D и 3D). Он также имеет эффективный битвектор с 1 бит на значение, а не 8 бит, как это делает boolean[].

Однако разреженные матрицы не поддерживают биты напрямую - только удваиваются и объекты. Вы можете обернуть 1D разреженную двойную матрицу, сопоставив бит-индекс с длинными индексами (bitIndex>>6), так как каждый длинный содержит 64 бита, convert извлеченный двойной необработанное длинное значение и использование битовых манипуляций для доступа к битам полученного длинного значения. Небольшая работа, но нигде не ближе, чем реализация разреженного вектора. После того, как ваша обертка работает, вы можете избежать преобразования удвоений в longs и реализовать реальную разреженную длинную 1d-матрицу, используя исходный код Colt для двойной разрешенной матрицы 1D в качестве отправной точки.

EDIT: дополнительная информация. Для векторов/матриц Colt для хранения не требуется память, предполагая, что все биты (longs) изначально равны 0. Установка значения в ненулевое значение потребляет память. Установка значения обратно в 0 продолжает потреблять память, хотя память для нулевых значений периодически регенерируется.

Если бит по-настоящему разрежен, так что для каждого базового длинного значения установлен только один бит, тогда накладные расходы на хранение будут очень низкими, для чего необходимо сохранить 64 бит на фактический бит. Но, как вы говорите, типичный случай на 20-40% разрежен, тогда накладные расходы будут намного ниже, и, возможно, не будут потрачены впустую, если биты группируются в диапазонах, например. биты от 0 до 100, затем 1000-1100 и 2000-2200 (значения в шестнадцатеричном формате). В целом только 1/16 региона назначается битам, но кластеризация означает, что биты хранятся без пробелов.

Ответ 2

TL; DR перейти сюда Эффективная реализация разреженного битового набора в Java

Я знаю, что это "старый" вопрос, но с тем же вопросом я наткнулся на этот пост. Хотя ответы хорошие, я был в конечном счете не удовлетворен. После дальнейшего копания, я думаю, что я столкнулся с "окончательным" ответом на вопрос о разреженных битах в Java.

В этой презентации автор, д-р Брюс Хаддон, обсуждает усилия своих исследователей по созданию высокоэффективной и высокопроизводительной замена стандартного Java BitSet.

Оригинальные ссылки на его презентацию мертвы, но я связался с доктором Хэддоном и сохранил здесь код и презентацию:

https://github.com/brettwooldridge/SparseBitSet

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

Слайды: это компьютерная наука, разработка программного обеспечения или хакинг?

Ответ 3

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

Если плотность превышает несколько процентов, вы можете использовать хэш-таблицу с индексом бит, деленную на 64, и хранить слова long в хэш-таблице, содержащей фактические биты. Бит N устанавливается, если хэш-таблица содержит значение V для int (N/64) и (V → (N mod 64)) & 1 истинно.

Оба этих ответа предполагают, что вы хотите оптимизировать произвольный доступ к битам. Если вы хотите оптимизировать последовательный (или другой доступ) к битам по индексу, то вам может понадобиться разреженная матричная структура, используя однообразное представление вектора нижнего уровня в зависимости от ожидаемой плотности. См. Разреженные матрицы

Ответ 4

Вы можете попробовать Карта дерева AVU FastUtil.

Ответ 5

CERN COLT широко используется для вычисления векторов и матриц и имеет разреженные матрицы, но специально не используется для бит-векторов.

http://acs.lbl.gov/software/colt/api/cern/colt/matrix/impl/SparseObjectMatrix1D.html

Ответ 6

Хэш-таблица, где простое присутствие или отсутствие ключа говорит вам что-то? Тогда это будет хэш! Я скептически отношусь к производительности набора (даже хэшированного) над BitSet. Это действительно зависит от того, является ли скорость или память основным драйвером.

Ответ 7

Вы можете попробовать библиотеку JavaEWAH.

https://code.google.com/p/javaewah/

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

(Используется Apache Hive и другими.)