Collections in Go language are generally represented by map[T]bool, and T represents element type. Although it is very flexible to represent a collection with a map type, we can represent it in a better form.
For example, in the field of data flow analysis, the set element is usually a non-negative integer, the set will contain many elements, and the set will often perform union and intersection operations. In this case, the bit array will perform more ideally than the map.
A bit array is usually represented by an unsigned number or a slice called "word", and each bit of each element represents a value in the set. When the i-th bit of the set is set, we say that this set contains element i.
The following program shows a simple bit array type and implements three functions to operate on this bit array:
package main
import (
"bytes"
"fmt"
)
// An IntSet is a set of small non-negative integers.
// Its zero value represents the empty set.
type IntSet struct {
words []uint
}
const (
bitNum = (32 << (^uint(0) >> 63)) //According to the platform, decide whether it is 32 or 64)
// Has reports whether the set contains the non-negative value x.
func (s *IntSet) Has(x int) bool {
word, bit := x/bitNum, uint(x%bitNum)
return word < len() && [word]&(1<<bit) != 0
}
// Add adds the non-negative value x to the set.
func (s *IntSet) Add(x int) {
word, bit := x/bitNum, uint(x%bitNum)
for word >= len() {
= append(, 0)
}
[word] |= 1 << bit
}
//The intersection of A and B, merge A and B// UnionWith sets s to the union of s and t.
func (s *IntSet) UnionWith(t *IntSet) {
for i, tword := range {
if i < len() {
[i] |= tword
} else {
= append(, tword)
}
}
}
Because each word has 64 binary bits, in order to locate the bit bit of x, we use the quotient of x/64 as the subscript of the word, and use the value obtained by x%64 as the location of the bit in this word.
For example, for the number 1, add it to the bit array:
func (s *IntSet) Add(x int) {
word, bit := x/bitNum, uint(x%bitNum) //0, 1 := 1/64, uint(1%64)
for word >= len() { // The conditions are not met = append(, 0)
}
[word] |= 1 << bit // [0] |= 1 << 1
}
// Bundle1After deposit，wordsThe array becomes[]uint64{2}
Similarly, if we add 66 to the bit array:
func (s *IntSet) Add(x int) {
word, bit := x/bitNum, uint(x%bitNum) //1, 2 := 66/64, uint(66%64)
for word >= len() { // The conditions are met = append(, 0) // At this time = []uint64{2, 0} }
[word] |= 1 << bit // [1] |= 1 << 2
}
// Keep putting it66After deposit，wordsThe array becomes[]uint64{2, 4}
Therefore, for words, there are 64 values that can be stored per element, and for every 64 more, a carry is added, that is, one element is added. (Note that 0 also occupies one, so 64 needs to carry, and the first element can be stored 0-63).
Therefore, for an element in words, when converting it to a specific value: first take its position i, use 64 * i as the carried number (similar to carrying every 10 digits), then convert this element into a binary number, count from right to left, and the number of digits is 1, which means that the corresponding value is present, and use this digit x+64 *i to be the value we stored.
Correspondingly, there can be the following String() function
// String returns the set as a string of the form "{1 2 3}".
func (s *IntSet) String() string {
var buf
('{')
for i, word := range {
if word == 0 {
continue
}
for j := 0; j < bitNum; j++ {
if word&(1<<uint(j)) != 0 {
if () > len("{") {
(' ')
}
(&buf, "%d", bitNum*i+j)
}
}
}
('}')
return ()
}
For example, after 1 and 66 are stored in the previous process, the conversion process is:
// []uint64{2 4}
// For 2: 1 << 1 = 2; so x = 0 * 64 + 1// For 4: 1 << 2 = 4; so x = 1 * 64 + 2// So convert toStringfor{1 66}
Other methods to implement bit arrays
func (s *IntSet) Len() int {
var len int
for _, word := range {
for j := 0; j < bitNum; j++ {
if word&(1<<uint(j)) != 0 {
len++
}
}
}
return len
}
func (s *IntSet) Remove(x int) {
word, bit := x/bitNum, uint(x%bitNum)
if (x) {
[word] ^= 1 << bit
}
}
func (s *IntSet) Clear() {
= append([]uint{})
}
func (s *IntSet) Copy() *IntSet {
intSet := &IntSet{
words: []uint{},
}
for _, value := range {
= append(, value)
}
return intSet
}
func (s *IntSet) AddAll(args ...int) {
for _, x := range args {
(x)
}
}
//The union of A and B, both A and B appearfunc (s *IntSet) IntersectWith(t *IntSet) {
for i, tword := range {
if i >= len() {
continue
}
[i] &= tword
}
}
//The difference between A and B, the element appears in A but not in Bfunc (s *IntSet) DifferenceWith(t *IntSet) {
t1 := () //In order not to change the transmission parameter, copy a copy (s)
for i, tword := range {
if i < len() {
[i] ^= tword
}
}
}
//The difference between A and B, the element appears in A and does not appear in B, or appears in B and does not appear in Afunc (s *IntSet) SymmetricDifference(t *IntSet) {
for i, tword := range {
if i < len() {
[i] ^= tword
} else {
= append(, tword)
}
}
}
//Get the slice collection of all elements in the bit arrayfunc (s *IntSet) Elems() []int {
var elems []int
for i, word := range {
for j := 0; j < bitNum; j++ {
if word&(1<<uint(j)) != 0 {
elems = append(elems, bitNum*i+j)
}
}
}
return elems
}
So far, all the common methods and functions of bit arrays have been implemented, and you can now use it.
func main() {
var x, y IntSet
(1)
(144)
(9)
("x:", ()) // "{1 9 144}"
(9)
(42)
("y:", ()) // "{9 42}"
(&y)
("x unionWith y:", ()) // "{1 9 42 144}"
("x has 9,123:", (9), (123)) // "true false"
("x len:", ()) //4
("y len:", ()) //2
(42)
("x after Remove 42:", ()) //{1 9 144}
z := ()
("z copy from x:", ()) //{1 9 144}
()
("clear x:", ()) //{}
(1, 2, 9)
("x addAll 1,2,9:", ()) //{1 2 9}
(&y)
("x intersectWith y:", ()) //{9}
(1, 2)
("x addAll 1,2:", ()) //{1 2 9}
(&y)
("x differenceWith y:", ()) //{1 2}
(9, 144)
("x addAll 9,144:", ()) //{1 2 9 144}
(&y)
("x symmetricDifference y:", ()) //{1 2 42 144}
for _, value := range () {
(value, " ") //1 2 42 144
}
}
The above is personal experience. I hope you can give you a reference and I hope you can support me more. If there are any mistakes or no complete considerations, I would like to give you advice.