inset（集合）
# Bit 数组（集合）
本例子来源于《Go语言圣经》。
提示：bitmap（位图）也是这样实现的。
Go 语言里的集合一般会用map[T]bool这种形式来表示，T 代表元素类型。集合用 map 类型来表示虽然非常灵活，但我们可以以一种更好的形式来表示它。例如在数据流分析领域，集合元素通常是一个非负整数，集合会包含很多元素，并且集合会经常进行并集、交集操作，这种情况下，bit 数组会比 map 表现更加理想。
# 实现intset
一个 bit 数组通常会用一个无符号数或者称之为“字”的 slice 来表示，每一个元素的每一位都表示集合里的一个值。当集合的第i位被设置时，我们才说这个集合包含元素i。下面的这个程序展示了一个简单的bit数组类型，并且实现了三个函数来对这个 bit 数组来进行操作：
gopl.io/ch6/intset
// unitSize is unit size
const unitSize = 32 << (^uint(0) >> 63)
// An IntSet is a set of small non-negative integers.
// Its zero value represents the empty set.
type IntSet struct {
words []uint
}
// Has reports whether the set contains the non-negative value x.
func (s *IntSet) Has(x int) bool {
word, bit := x/unitSize, uint(x%unitSize)
return word < len(s.words) && s.words[word]&(1<<bit) != 0
}
// Add adds the non-negative value x to the set.
func (s *IntSet) Add(x int) {
word, bit := x/unitSize, uint(x%unitSize)
for word >= len(s.words) {
s.words = append(s.words, 0)
}
s.words[word] |= 1 << bit
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
因为每一个字都有 64 个二进制位，所以为了定位 x 的 bit 位，我们用了x/64的商作为字的下标，并且用x%64得到的值作为这个字内的bit的所在位置。
32 << (^uint(0) >> 63)表达式可以智能判断平台是 32 位还是 64 位。
var x, y insert.IntSet
x.Add(1)
x.Add(144)
x.Add(9)
fmt.Println(x.String()) // "{1 9 144}"
y.Add(9)
y.Add(42)
fmt.Println(y.String()) // "{9 42}"
fmt.Println(x.Has(9), x.Has(123)) // "true false"
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
# String方法
为 Bit 数组实现String方法：
// String returns the set as a string of the form "{1 2 3}".
func (s *IntSet) String() string {
var buf bytes.Buffer
buf.WriteByte('{')
for i, word := range s.words {
if word == 0 {
continue
}
for j := 0; j < unitSize; j++ {
if word&(1<<uint(j)) != 0 {
if buf.Len() > len("{") {
buf.WriteByte(' ')
}
fmt.Fprintf(&buf, "%d", unitSize*i+j)
}
}
}
buf.WriteByte('}')
return buf.String()
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
这里忽略掉fmt.Fprintf的报错。
# Len、Remove、Clear和Copy方法
// Len returns the numbers of elements.
func (s *IntSet) Len() int {
result := 0
for _, word := range s.words {
if word == 0 {
continue
}
for j := 0; j < unitSize; j++ {
if word&(1<<uint(j)) != 0 {
result++
}
}
}
return result
}
// Elems returns all element of the set.
func (s *IntSet) Elems() []int {
result := make([]int, 0)
for i, word := range s.words {
if word == 0 {
continue
}
for j := 0; j < unitSize; j++ {
if word&(1<<uint(j)) != 0 {
result = append(result, i*unitSize+j)
}
}
}
return result
}
// Remove removes x from the set.
func (s *IntSet) Remove(x int) {
word, bit := x/unitSize, uint(x%unitSize)
if word > len(s.words) {
return
}
s.words[word] &^= 1 << bit
}
// Clear removes all elements from the set.
func (s *IntSet) Clear() {
s.words = nil
}
// Copy copies the set and returns the replicated set.
func (s *IntSet) Copy() *IntSet {
newWords := make([]uint, len(s.words))
copy(newWords, s.words)
return &IntSet{words: newWords}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
这几个方法都是通过 bit 操作实现的。
fmt.Println(x.Len(), y.Len()) // 3 2
x.Remove(1)
y.Remove(42)
fmt.Println(x.String()) // "{9 144}"
fmt.Println(y.String()) // "{9}"
xx := x.Copy()
x.Clear()
fmt.Println(x.String()) // "{}"
fmt.Println(xx.String()) // "{9 42}"
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
# 变参方法
// AddAll adds the no-negative values to the set.
func (s *IntSet) AddAll(values ...int) {
for _, value := range values {
s.Add(value)
}
}
1
2
3
4
5
6
2
3
4
5
6
x.AddAll(1, 2, 3, 4)
fmt.Println(x.String())
1
2
2
# 并集
并集：将 A 集合和 B 集合的元素合并在一起。
// UnionWith sets s to the union of s and t.
func (s *IntSet) UnionWith(t *IntSet) {
/*
s: 1 0 1 1 0
t: 1 1 0 1 0
s: 1 1 1 1 0
*/
for i, tword := range t.words {
if i < len(s.words) {
s.words[i] |= tword
} else {
s.words = append(s.words, tword)
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
UnionWith这个方法里用到了 bit 位的“或”逻辑操作符号|来一次完成 64 个元素的或计算。
x.UnionWith(&y)
fmt.Println(x.String()) // "{1 9 42 144}"
1
2
2
# 交集
交集：元素在 A 集合 B 集合均出现。
// IntersectWith sets s to the intersection of s and t.
func (s *IntSet) IntersectWith(t *IntSet) {
/*
s: 1 0 1 1 0
t: 1 1 0 1 0
s: 1 0 0 1 0
*/
minLen := len(s.words)
if len(t.words) < minLen {
minLen = len(t.words)
}
for i, tword := range t.words {
if i == minLen {
break
}
s.words[i] &= s.words[i] & tword
}
for i := minLen; i < len(s.words); i++ {
s.words[i] = 0
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
x.IntersectWith(&y)
fmt.Printf(x.String()) // "{9}"
1
2
2
# 差集
差集：元素出现在 A 集合，未出现在 B 集合。
// DifferenceWith sets s to the difference of s and t.
func (s *IntSet) DifferenceWith(t *IntSet) {
/*
s: 1 0 1 1 0
t: 1 1 0 1 0
s: 0 0 1 0 0
*/
for i, tword := range t.words {
if i < len(s.words) {
s.words[i] &= s.words[i] ^ tword
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
x.DifferenceWith(&y)
fmt.Printf(x.String()) // "{1 144}"
1
2
2
# 并差集
并差集：元素出现在 A 但没有出现在 B，或者出现在 B 没有出现在 A。
// SymmetricDifference sets s to the union difference of s and t.
func (s *IntSet) SymmetricDifference(t *IntSet) {
/*
s: 1 0 1 1 0
t: 1 1 0 1 0
s: 0 1 1 0 0
*/
for i, tword := range t.words {
if i < len(s.words) {
s.words[i] = s.words[i]&(s.words[i]^tword) | (tword & (s.words[i] ^ tword))
} else {
s.words = append(s.words, tword)
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
x.SymmetricDifference(&y)
fmt.Printf(x.String()) // "{1 42 144}"
1
2
2
上次更新: 2024/05/29, 06:25:22