第二章

  • 名称
  • 声明
  • 变量
  • 赋值
  • 类型声明
  • 包和文件
  • 作用域

练习2.1:

添加类型、常量和函数到tempconv包中,处理以开尔文为单位(K)的温度值,0K=-273.15℃,变化1K和变化1℃是等价的

  • 很水的题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
package tempconv
import "fmt"
type Kelvin float64
type Celsius float64
func (k Kelvin) String() string {
return fmt.Sprintf("%gK", k)
}
func CToK(c Celsius) Kelvin {
return Kelvin(c - 273.15)
}
func KToC(k Kelvin) Celsius {
return Celsius(k + 273.15)
}
练习2.2

写一个类似于cf的通用的单位转换程序,从命令行参数或者标准输入(如果没有参数)获取数字,然后将每一个数字转换为以摄氏温度和华氏温度表示的温度,以英寸和米表示的长度单位,以磅和千克表示的重量单位,等等

  • 略,同很水

练习2.3:

使用循环重写PopCount来代替单个表达式.对比两个版本的效率

  • 下面连续三道题都是经典面试题,求二进制数中1的个数,限定了正整数
  • 书上的代码主要是预先计算,将64bit每8bit一组,8bit会有二的八次方种结果,共256种结果,将所有的结果都先计算出来(空间换时间)
  • 预计算主要是这一步pc[i] = pc[i/2] + byte(i&1),注意此处的含义是除以二表示二进制数右移一位,后面表示最后一位是1还是0
  • 代码中[256]byte换成[256]int,更好理解。可能这样写只是为了让人更加能搞明白byte和int的各种转换吧
  • 注意这种预计算的执行效率是很高的

书上给的代码还是比较扭曲的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 2000000000 0.32 ns/op
package tempconv
var pc [256]byte
func init() {
for i := range pc {
pc[i] = pc[i/2] + byte(i&1)
}
}
func PopCount(x uint64) int {
return int(pc[byte(x>>(0*8))] +
pc[byte(x>>(1*8))] +
pc[byte(x>>(2*8))] +
pc[byte(x>>(3*8))] +
pc[byte(x>>(4*8))] +
pc[byte(x>>(5*8))] +
pc[byte(x>>(6*8))] +
pc[byte(x>>(7*8))])
}

改成循环

  • 惊不惊喜,意不意外,速度居然爆降低100倍
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func PopCount1(x uint64) int {
ret := byte(0)
for i := uint8(0); i < 8; i++ {
ret += pc[byte(x>>(i*8))]
}
return int(ret)
}
func BenchmarkPopCount1(b *testing.B) {
// 100000000 21.4 ns/op
// 循环
for i := 0; i < b.N; i++ {
PopCount1(2<<63 - 1)
}
}

练习2.4

写一个用于统计位的PopCount,它在其实际参数的64位上执行移位操作,每次判断最右边的位,进而实现统计功能.把它与快查表版本的性能进行对比

  • 很普通的写法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func PopCount2(x uint64) int {
ret := 0
for i := 0; i < 64; i++ {
if x&1 == 1 {
ret += 1
}
x = x >> 1
}
return ret
}
func BenchmarkPopCount2(b *testing.B) {
// 20000000 60.5 ns/op
// >> 循环
for i := 0; i < b.N; i++ {
PopCount2(2<<63 - 1)
}
}

练习2.5

使用x&(x-1)可以清除x最右边的非零位,利用该特点写一个PopCount,然后评价它的性能

  • x&(x-1)面试基础题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func PopCount3(x uint64) int {
ret := 0
for x != 0 {
x = (x - 1) & x
ret += 1
}
return ret
}
func BenchmarkPopCount3(b *testing.B) {
// 30000000 50.5 ns/op
// x&(x-1)
for i := 0; i < b.N; i++ {
PopCount3(2<<63 - 1)
}
}

最后~~~还是挺奇葩,书上的写法居然是最快的,改成循环速度居然爆降,也不知道Go编译器是如何优化代码的╭(╯^╰)╮