Подробное введение в то, как bitset реализован в Go

задняя часть Go

Недавно я попытался записать несколько небольших видеороликов на станции B, мойДомашняя страница станции B. Запись видео должна быть последним шагом, чтобы досконально разобраться в каком-то пункте знаний, и в то же время надеяться приобрести какие-то дополнительные способности. Говоря о том, как Go реализует набор битов, мне было немного сложно об этом говорить. Подумав, я решил объяснить это с помощью текста, дополненного видео, поэтому и написал эту статью.

Соответствующий код был размещен на github по следующему адресу:go-set-example

Если вы найдете что-то не так, пожалуйста, поправьте меня, спасибо.

структура набора битов

Ранее я писал статью под названиемКак использовать сеты в GoСтатья, в которой представлен один из простейших сценариев применения битсета, бит флага состояния, а также, кстати, упоминается идея реализации битсета.

В чем разница между флагами состояния и обычными коллекциями?

Мой вывод заключается в том, что количество элементов во флаге состояния обычно фиксировано. В общих коллекциях количество элементов обычно меняется динамически. Какую проблему это может вызвать?

В общем, мы используем целое число для представления всех состояний во флаге состояния.Самый большой тип int64 имеет 64 двоичных бита и может содержать до 64 элементов, что вполне достаточно. Но в случае наборов количество элементов и значений обычно не фиксированы.

Например, коллекция наборов битов может изначально содержать только 1, 2 и 4 элемента, которые могут быть представлены только одним int64. следующим образом:

Но если вы добавите еще один элемент, например 64 (диапазон представления int64 0-63), это выходит за пределы диапазона, который может представлять int64. что делать?

Int64 не может быть представлен, поэтому используйте несколько. Структура на данный момент следующая:

Слайс int64 точно вписывается в приведенную выше структуру. Затем мы можем определить новый типBitSet,следующим образом:

type BitSet struct {
	data []int64
	size int
}

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

Кроме того, поскольку количество элементов в наборе битов не может передаватьсяlenПриобретение функции и конкретный метод относительно сложны, вы можете добавить поле размера для записи количества элементов набора. Затем вы можете добавитьSizeметод.

func (set *BitSet) Size() int {
	return set.size
}

положение элемента

определенныйBitSetтип, и возникает новая проблема, как определить местонахождение элемента? В случае флагов значением элемента является позиция, поэтому этот вопрос не рассматривается. Но это не относится к универсальным коллекциям.

Первый взглядBitSetРаспределение двоичных битов.

Подобно эффекту строк и столбцов, если предположить, что сindexпредставляет строку (индекс),posПредставляет столбец (позицию). Индексы срезов находятся в диапазоне от 0 до n, где n относится к самому большому элементу в коллекции.

Далее определитеindexа такжеposценность . На самом деле предыдущая статья уже представила.

indexДлина слова делится на значение элемента, т.е.value / 64, что приводит к эффективным побитовым операциям, т.е.value >> 6.

posВы можете взять длину слова по модулю по значению элемента, то естьvalue % 64, что приводит к эффективным побитовым операциям, т.е.value & 0x3f, получить соответствующую позицию, а затем использовать1 << uint(value % 0xf)чтобы преобразовать позицию в значение.

Код

Никакого количества теорииshow me your code. Приступаем к кодированию!

Сначала определите некоторые константы.

const (
	shift = 6    // 2^n = 64 的 n
	mask  = 0x3f // n=6，即 2^n - 1 = 63，即 0x3f
)

используется для расчетаindexа такжеposиз двух констант.

Для удобства предусмотрены две функцииindexа такжеposРасчет соответствующего значения выше, код выглядит следующим образом:

func index(n int) int {
	return n >> shift
}

// 相对于标志位使用场景中某个标志的值
func posVal(n int) uint64 {
	return 1 << uint(n&mask)
}

Конструктор

Предусмотрена функция для создания начальногоBitSetи поддерживает установку начального элемента.

Прототип функции выглядит следующим образом:

func NewBitSet(ns ...int) *BitSet {
	// ...
}

Выходные параметрыnsЯвляетсяintПараметр переменной длины типа для установки начального значения в коллекции.

Если входной параметрnsЕсли он пуст,new(BitSet)Просто верните пустую коллекцию.

if len(ns) == 0 {
	return new(BitSet)
}

Если длина не пуста, пространство, которое нужно открыть, рассчитывается путем вычисления максимального элементаindexможно определить.

// 计算多 bitset 开辟多个空间
max := ns[0]
for _, n := range ns {
	if n > max {
		max = n
	}
}

// 如果 max < 0，直接返回空。
if max < 0 {
	return new(BitSet)
}

// 通过 max >> shift+1 计算最大值 max 所在 index
// 而 index + 1 即为要开辟的空间
s := &BitSet{
	data: make([]int64, index(max)+1),
}

Теперь можноBitSetдобавляются элементы.

for _, n := range ns {
	if n >= 0 {
		// e >> shift 获取索引位置，即行，一般叫 index
		// e&mask 获取所在列，一般叫 pos，F1 0 F2 1
		s.data[n>>shift] |= posVal(n)
		// 增加元素个数
		s.size++
	}
}

// 返回创建的 BitSet
return s

Все элементы добавлены!

Методы BitSet

Теперь дело заBitSetДобавьте несколько методов. В основном он делится на две категории: одна - это общие основные методы, такие как добавление, удаление и поиск, а другая - уникальная операция набора, пересечения и разности.

основной метод

В основном существует несколько методов, а именноAdd(Увеличивать),Clear(Чисто) ,Contains(проверить) и возвращает количество элементов. Для лучшей производительности и использования пространства,Addа такжеClearТакже учитывайте гибкость.

contains

первыйContains, то есть проверить, существует ли элемент.

Функция определяется следующим образом:

func (set *BitSet) Contains(n int) bool {
	...
}

Входным параметром является проверяемый элемент, а выходным — результат проверки.

Код реализации выглядит следующим образом:

// 获取元素对应的 int64 的位置，如果超出 data 能表示的范围，直接返回。
i := index(n)
if i >= len(set.data) {
	return false
}

return set.data[i]&posVal(n) != 0

ядроset.data[i]&posVal(n) != 0Этот код используется для определения того, существует ли указанный элемент.

clear

Давай поговоримClear, удаляет элемент из коллекции,

Функция определяется следующим образом:

func (set *BitSet) Clear(n int) *BitSet {
	// ...
}

Код реализации выглядит следующим образом:

// 元素不能小于 0
if n < 0 {
	return set
}

// 计算切片索引位置，如果超出当前索引表示的范围，返回即可。
i := index(n)
if i >= len(set.data) {
	return set
}

// 检查是否存在元素
if d[i]&posVal(n) != 0 {
	set.data[i] &^= posVal(n)
	set.size--
}

пройти через&^Реализует указанный бит очистки. Также помнитеset.size--Обновите значение элемента в коллекции.

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

Как это работает?

через паруset.dataВыполнить проверку, проверить первый ненулевой из старшего разрядаuint64, основываясь на этомreslice. Предположим, этот метод называетсяtrim.

Код реализации выглядит следующим образом:

func (set *Set) trim() {
	d := set.data
	n := len(d) - 1
	for n >= 0 && d[n] == 0 {
		n--
	}
	set.data = d[:n+1]
}

add

Тогда скажиAddМетод для добавления элемента в коллекцию.

Функция определяется следующим образом:

func (set *BitSet) Add(n int) *BitSet {
	...
}

При добавлении элементов сначала проверьте, достаточно ли места для новых элементов. Если позиция индекса нового элемента в настоящее время неdataУказанный диапазон необходимо расширить.

Реализация выглядит следующим образом:

// 检测是否有足够的空间存放新元素
i := index(n)
if i >= len(set.data) {
	// 扩容大小为 i+1
	ndata := make([]uint64, i+1)
	copy(ndata, set.data)
	set.data = ndata
}

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

Код реализации выглядит следующим образом:

if set.data[i]&posVal(n) == 0 {
	// 设置元素到集合中
	set.data[i] |= posVal(n)
	s.size++
}

Отлично! Так об основных методах.

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

метод сбора

После введения основных методов продолжайте вводить некоторые уникальные методы сбора, пересечения и разности.

computeSize

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

Код реализации выглядит следующим образом:

func (set *BitSet) computeSize() int {
	d := set.data
	n := 0
	for i, len := 0, len(d); i < len; i++ {
		if w := d[i]; w != 0 {
			n += bits.OnesCount64(w)
		}
	}

	return n
}

Это неэкспортируемый метод, и его следует использовать только внутри страны. траверсdataкаждогоuint64, если не 0, подсчитать количество элементов в нем. Количество элементов подсчитывается с помощью стандартной библиотекиbits.OnesCount64метод.

определение метода

Продолжайте вводить несколько методов сбора, их определения аналогичны, все ониBitSetс другимBitSetОперация выглядит следующим образом:

// 交集
func (set *BitSet) Intersect(other *BitSet) *BitSet {
	// ...
}
// 并集
func (set *BitSet) Union(other *BitSet) *BitSet {
	// ...
}
// 差集
func (set *BitSet) Difference(other *BitSet) *BitSet {
	// ...
}

intersect

Представить первымIntersect, то есть метод вычисления пересечения.

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

Код реализации выглядит следующим образом:

// 首先，获取这个小范围的集合的长度
minLen := min(len(set.data), len(other.data))

// 以 minLen 开辟空间
intersectSet := &BitSet{
	data: make([]uint64, minLen),
}

// 以 minLen 进行遍历计算交集
for i := minLen - 1; i >= 0; i-- {
	intersectSet.data[i] = set.data[i] & other.data[i]
}

intersectSet.size = set.computeSize()

Здесь один за другим, обходя каждыйuint64воплощать в жизнь与运算добиться пересечения. После завершения операции не забудьте рассчитатьintersectSetКоличество элементов вsizeценность .

union

возвращение в союзUnionметод.

его вычислительная логика иIntersectНапротив. Сумма пространства, занимаемого результатом объединения, основана на большем наборе из двух наборов, участвующих в операции.

Код реализации выглядит следующим образом:

var maxSet, minSet *BitSet
if len(set.data) > len(other.data) {
	maxSet, minSet = set, other
} else {
	maxSet, minSet = other, set
}

unionSet := &BitSet{
	data: make([]uint64, len(maxSet.data)),
}

созданныйunionSetсередина,dataВыделенное пространствоlen(maxSet.data).

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

minLen := len(minSet.data)
copy(unionSet.data[minLen:], maxSet.data[minLen:])

Наконец, переберите обе коллекцииdata,пройти через或运算Вычислите остаток.

for i := 0; i < minLen; i++ {
	unionSet.data[i] = set.data[i] | other.data[i]
}

// 更新计算 size
unionSet.size = unionSet.computeSize()

difference

Представляем последний метод, связанный с коллекцией,Difference, то есть разностная операция.

Результат расчета разницыdifferenceSetВыделенное пространство определяется вычитаемым наборомsetПринимать решение. другие операции иIntersectа такжеUnionАналогично, побитовые операции через&^выполнить.

setLen := len(set.data)

differenceSet := &BitSet{
	data: make([]uint64, setLen),
}

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

minLen := setLen
if setLen > otherLen {
	copy(differenceSet.data[otherLen:], set.data[otherLen:])
	minLen = otherLen
}

записыватьminLenдля последующих битовых операций.

// 遍历 data 执行位运算。
for i := 0; i < minLen; i++ {
	differenceSet.data[i] = set.data[i] &^ other.data[i]
}

differenceSet.size = differenceSet.computeSize()

перебирать элементы коллекции

Об обходе элементов коллекции поговорим отдельно, перед просмотром элементов коллекции мы всегда проходилиContainsметод проверки существования. Можно ли обойти все элементы коллекции?

Давайте посмотрим на структуру набора битов следующим образом:

В приведенном выше наборе первая строкаint64Первый элемент равен 1, а завершающий бит равен нулю. Путем наблюдения обнаруживается, что впереди несколько нулей, а первый элемент — это какое значение.

вторая линияint64Первый элемент не имеет конечного 0, поэтому его значение равно 0? Нет, конечно, есть еще 64-битная база предыдущей строки, поэтому ее значение равно 64+0.

Вы нарисовали какие-то правила? Глупый, теоретическая база слишком бедна, полна понимания, просто чувствую, что письмо не ясно. Проверьте код!

Сначала посмотрите на определение функции:


func (set *BitSet) Visit(do func(int) (skip bool)) (aborted bool) {
	//...
}

Входным параметром является callback-функция, через которую получается значение элемента, иначе невозможно каждый раз писать большую серию логики работы цикла. Возвращаемое значение функции обратного вызоваbool, указывающий, следует ли продолжать обход.VisitВозвращаемое значение указывает на аварийное завершение функции.

Код реализации выглядит следующим образом:

d := set.data
for i, len := 0, len(d); i < len; i++ {
	w := d[i]
	if w == 0 {
		continue
	}

	// 理论功力不好，不知道怎么描述了。哈哈
	// 这小段代码可以理解为从元素值到 index 的逆运算，
	// 只不过得到的值是诸如 0、64、128 的第一个位置的值。
	// 0 << 6，还是 0，1 << 6 就是 64，2 << 6 的就是 128
	n := i << shift 
	for w != 0 {
		// 000.....000100 64~128 的话，表示 66，即 64 + 2，这个 2 可以由结尾 0 的个数确定
		// 那怎么获取结果 0 的个数呢？可以使用 bits.TrailingZeros64 函数
		b := bits.TrailingZeros64(w)
		if do(n + b) {
			return true
		}
		// 将已经检查的位清零
		// 为了保证尾部 0 的个数能代表元素的值
		w &^= 1 << uint64(b) 
	}
}

Он также очень удобен в использовании.Пример кода выглядит следующим образом:

set := NewBitSet(1, 2, 10, 99)
set.Visit(func(n int) bool {
	fmt.Println(n)
	return false
})

Ладно, хватит говорить!

Суммировать

В этой статье в основном представлена ​​реализация набора битов на основе нескольких пакетов с открытым исходным кодом, таких какbitа такжеbitsetЖдать. В общем, битовые операции не такие интуитивные и чувствуются, что мозгов не хватает.

понимание

В последнее время я глубоко копался в языке Go, и постепенно обнаружил некоторые свои недостатки, постепенно выявился недостаток теоретических знаний. Например, при написании этой статьи я узнал, что стандартная библиотека bits использует德布鲁因序列, раньше было непонятно. Несколько дней назад, когда я изучал, как парсить JSON, я узнал о знаниях конечных автоматов, Исходный код Go прекрасно отражает важность этих знаний. Изучая языковую композицию Go, я знаю扩展巴克斯范式, документация многих языков так выражает грамматику, понятно.

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

Категории