第二章

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

练习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编译器是如何优化代码的╭(╯^╰)╮