Как эффективно хранить большие битовые маски?

Question

[uvelichitel]

Бывает нужен []bit для алгоритмических задач с требованиями по памяти. bool использует byte а не bit(на моей машине)
fmt.Println(unsafe.Sizeof([1000]bool{}))//Печатает 1000. И это в байтах а не в битах https://golang.org/pkg/unsafe/#Sizeof
Появился интересный "math/bits" в stdlib, но он ограничен по величине uint64 и не имеет тривиальных методов get(n) set(n).
Посоветуйте где покопать. Код не обязателен, достаточно подходов. Что ли лепить свой тип из []uint64 и обвешивать методами?

Answer 1

[Александр Павлюк]

Можете использовать https://godoc.org/github.com/golang-collections/go...

Или написать свою имплементацию на основе []byte, например. Сдвигами или масками доставать нужный вам бит.

Answer 2

[Леонид Николаев]

https://goplay.space/#aBmYRHvEg6u

думаю, что вот так надо, наверное. если я правильно понял вопрос. просто побитово сравниваем

Comments

[uvelichitel]

Мне нужно хранить битовый массив вроде 11010001110001111000001111001110001100011... очень длинный с возможностью добраться до n-ного бита. Вроде array.Get(9) - в данном случае 1, и установить его например в 0 - array.Set(9, 0). Вот я такого примерно хочу.

[Леонид Николаев]

я бы хранил бы основу как []uint64. 8 байт, считать смещение просто, делать логику для байта - тоже. а там уже можно обвязывать как угодно.

[Александр Павлюк]

Леонид Николаев, зачем именно []uint64? []byte ведь удобнее

[Леонид Николаев]

Да без разницы, конечно, просто наверное, даже одного элемента может хватить на многое.

[uvelichitel]

Александр Павлюк, []uint64 потому что есть готовая арифметика методов доступа. Для установки k-го бита
array[k/64] |= 1 << (k % 64)

[Andrey Tsvetkov]

uvelichitel, та же арифметика доступна и для слайса байт
array[k/8] |= 1 << (k % 8)

[Леонид Николаев]

Давайте так, у нас будет слайс, неизвестного размера. Кап у него мы тоже не сможем четко предсказать. Потому, чем больше элемент, тем реже надо будет делать аллок.

Я именно из этих соображений писал

[Александр Павлюк]

Леонид Николаев, что мешает массив байт аллоцировать кратно 8 байтам? ))
аллоки тут никак не влияют

[Леонид Николаев]

Ничего. Можно и по 128байт. Только хотел бы уточнить, как вы в го будет контролировать из какого куска брать память? Насколько я знаю - это программисту не доступно. Алгоритм удвоения кап и все такое.

Короче, размерность элементов - выбор каждого. Не вижу смысла продолжать это обсуждение.

Answer 3

[index0h]

В чем вы измеряете эффективность? В удобстве/памяти/производительности?

Comments

[uvelichitel]

Основная цель - память. Например для объемов википедии с соответствием слова одному биту. Из удобств в текущей задаче достаточно методов чтения и установки бита. По производительности ассимптотика всего решения крутится вокруг О(log(n)), не хотелось бы вылазить.

[uvelichitel]

index0h ,пишу полнотекстовый поиск на вейвлет деревьях вместо обратного индекса для экономии памяти, если вам интересно.))

[index0h]

uvelichitel, Если количество бит фиксировано - самый маленький объем будет занимать массив byte. Что-то типа такого , правда на сколько этим делом будет удобно пользоваться, я хз.