Библиотека для кольтов *1001* имеет разреженные матрицы (1D, 2D и 3D). Он также имеет эффективный BitVector, с 1 битом на значение, а не 8 битами, как boolean[].
Однако разреженные матрицы не поддерживают биты напрямую - только удваиваются и объекты. Вы можете обернуть 1D разреженную двойную матрицу, отобразив битовый индекс на длинные индексы (bitIndex>>6), поскольку каждый длинный содержит 64 бита, конвертирует извлеченное двойное в необработанное длинное значение и использует битовую манипуляцию для доступа к битам восстановленный долго. Небольшая работа, но далеко не так много, как реализация разреженного вектора самостоятельно. Как только ваша оболочка заработает, вы можете избежать преобразования двойных значений в длинные и реализовать реальную разреженную длинную 1d-матрицу, используя доступный исходный код Colt для двойной одномерной разреженной матрицы в качестве отправной точки.
РЕДАКТИРОВАТЬ: Подробнее. Векторы / матрицы Colt изначально не требуют памяти для хранения, при условии, что все биты (длинные) изначально равны 0. Установка значения, отличного от нуля, потребляет память. Установка значения обратно в 0 продолжает потреблять память, хотя память для нулевых значений периодически восстанавливается.
Если биты действительно разрежены, так что для каждого длинного значения резервирования установлен только один бит, тогда затраты на хранение будут очень низкими, требуя 64 бита на фактический сохраненный бит. Но, как вы упомянули, типичный случай составляет 20-40% разреженных, тогда издержки будут намного ниже, возможно, без потери памяти, если биты сгруппированы в диапазонах, например биты от 0 до 100, затем 1000-1100 и 2000-2200 (значения в шестнадцатеричном формате). В целом, только 1/16 области назначается битам, но кластеризация означает, что биты сохраняются без потерянного пространства.