第六章

  • 方法声明
  • 指针接收者的方法
  • 通过结构体内嵌组成类型
  • 方法变量与表达式
  • 示例: 位向量
  • 封装

这应该是整本书包含内容最少的章节了,因为和函数差不多，该章习题整个也是扩充位向量这个练习，比第五章练习简单太多

练习6.1:

实现这些附加的方法

1
2
3
4
func (*InSet) Len() int
func (*InSet) Remove(x int)
func (*InSet) Clear()
func (*InSet) Copy() *InSet
  • 首先需要注意的是，在该实现中位向量并不是完整的从左往右，在slice中每个元素是从右向左的
  • 书本上给出了稍微复杂的string实现,Len参照string就可以了
  • Remove就是将某二进制位置为0,比置为1稍微复杂一点，方案为左移后取反再求与运算
  • Clear实行slice的清空，slice[:0]即可
  • Copy，使用make新建一个同等长度的slice，再copy完全拷贝
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
func (s *IntSet) Len() int {
	ret := 0
	for _, word := range s.words {
		if word == 0 {
			continue
		}
		for j := 0; j < 64; j++ {
			if word&(1<<uint(j)) != 0 {
				ret += 1
			}
		}
	}
	return ret
}

func (s *IntSet) Remove(x int) {
	word, bit := x/64, uint(x%64)
	s.words[word] &= (^(1 << bit))
}

func (s *IntSet) Clear() {
	s.words = s.words[:0]
}

func (s *IntSet) Copy() *IntSet {
	newWords := make([]uint64, len(s.words))
	copy(newWords, s.words)
	return &IntSet{newWords}
}

练习6.2:

定义一个变长方法(*InSet).AddAll(…int),它允许接受一串整型值作为参数,比如s.AddAll(1,2,3)

  • 因为已经实现了Add方法，此处直接内部调用Add就可以了
1
2
3
4
5
func (s *IntSet) AddALL(values ...int) {
	for _, v := range values {
		s.Add(v)
	}
}

练习6.3:

(*InSet).UnionWith计算了两个集合的并集,使用|操作符对每个字符进行按位或操作.实现交集、差集和对称差运算(两个集合的对称差只包含某个集合中存在的元素)

  • 额~~~，搞个最简单的求并集好了….,最后得到结果覆盖一下原有的slice
1
2
3
4
5
6
7
func (s *IntSet) And(t *IntSet) {
	min := math.Min(len(s.words), len(t.words))
	for i := 0; i < min; i++ {
		s.words[i] &= t.words[i]
	}
	s.words = s.words[:min]
}

练习6.4:

添加方法Elems返回包含集合元素的slice,这适合在range循环中使用

  • 同Len方法,都是遍历,因此，从设计角度上说，应该string和len方法都直接依赖Elems的实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
func (s *IntSet) Elems() []int {
	var ret []int
	for i, word := range s.words {
		if word == 0 {
			continue
		}
		for j := 0; j < 64; j++ {
			if word&(1<<uint(j)) != 0 {
				ret = append(ret, 64*i+j)
			}
		}
	}
	return ret
}

练习6.5:

InSet使用的每个字符类型都是int64,但是64位的计算在32位平台上的效率不高.改写程序以使用uint类型,这是适应平台的无符号整型.除以64的操作可以使用一个常量来表示32位或者64位.你或许可以使用一个讨巧的表达式32<<(^uint(0)>>63)来表示除数

  • 该题只是从效率角度来提供了一种思路，顺便给了你一个trick，uint在32位平台使用32位长度,64位使用64长度,32<<(^uint(0)>>63), 当为32位的时候后面为0,得到32,为64的时候，后面为1得到64