我经常喜欢尝试解决前几年的代码难题的出现。如果您不知道Advent of Code是什么，请确保您检查一下。
tldr：代码的出现是针对各种技能和技能级别的小型编程难题的出现日历，可以用您喜欢的任何编程语言解决。
这篇文章是关于拼图2021/day-6我试图解决的，因为这个难题不是很有趣，但我发现它是
一个很好的例子，用于探索如何深入了解代码的性能，找到潜在的瓶颈并使用GO提供的工具进行改进。
代码出现的每个难题都包含两个部分。您需要解决第一个以移至第二个，通常第二个是第一个更为复杂或苛刻的变化。这也是我们在这篇文章中也将遵循的方法。
工具
我们要使用的工具是
- Benchmarks在go tool pprof的帮助下测量和分析GO代码的性能。
- Benchstat计算统计摘要并比较基准。
第1部分
我不会简洁地在这里重复这个问题，但是如果您仔细阅读了难题，您可能会像我第一次做的那样提出一个微不足道的解决方案。
func parseInput(s string) []int {
data := strings.Split(strings.Split(s, "\n")[0], ",")
fish := make([]int, len(data))
for i, d := range data {
fish[i] = MustAtoi(d)
}
return fish
}
func MustAtoi(s string) int {
n, err := strconv.Atoi(s)
if err != nil {
panic(err)
}
return n
}
func Solve(input string, days int) int {
fish := parseInput(input)
for i := 0; i < days; i++ {
tempFish := []int{}
for j := range fish {
if fish[j] == 0 {
fish[j] = 6
tempFish = append(tempFish, 8)
} else {
fish[j]--
}
}
fish = append(fish, tempFish...)
}
return len(fish)
}
我正在解析输入，并将其转换为数字列表，然后迭代days的数量。每天我都会减少每个鱼的计时器，如果计时器达到零重置为6，并且在临时列表中添加了带有计时器8的新鱼，那将在一天结束时将其附加在主列表中。几乎就是这样，成功地解决了第1部分，并且足够快。
ok advent-of-code/2021/go/day-6 0.226s
但是，这篇文章不够快，或者只是解决难题。
在开始代码更改之前，我们需要当前实现的基准作为基础
在优化之前始终测量。
var sink int
func BenchmarkSolution(b *testing.B) {
res := 0
input := util.ReadFile("input.txt")
b.ResetTimer()
b.ReportAllocs()
for i := 0; i < b.N; i++ {
res = Solve(input, 80)
}
sink = res
}
基准
我们可以用
运行基准
go test ./... -benchmem -run=^$ -v -bench ^Bench -memprofile naive.out -count=5 | tee naive.txt
在我的机器输出上运行基准
pkg: advent-of-code/2021/go/day-6
BenchmarkSolution
BenchmarkSolution-10 235 5210983 ns/op 31653556 B/op 1025 allocs/op
BenchmarkSolution-10 231 5086091 ns/op 31653547 B/op 1025 allocs/op
BenchmarkSolution-10 225 5146135 ns/op 31653549 B/op 1025 allocs/op
BenchmarkSolution-10 231 5191141 ns/op 31653571 B/op 1025 allocs/op
BenchmarkSolution-10 229 5104518 ns/op 31653558 B/op 1025 allocs/op
PASS
ok advent-of-code/2021/go/day-6 8.847s
除了上述输出外，启用了flag -memprofile内存分析，可以帮助识别与内存有关的瓶颈。
您可以使用交互式CLI接口进行浏览数据
go tool pprof naive.out
# and then list the data for Solve function with
list Solve
从此视图中，我们可以挖掘从基准测试中收集的分析数据，并易于发现分配内存的3个大罪犯。
通过减少不必要的内存分配可改善性能（例如，内存分配开销，垃圾收集卡赫友好行为）。
通常，在调查性能问题时，您会在每个代码更改上运行基准测试以验证您的更改并实际改进代码，但是对于简洁起见，我们将讨论所有改进，然后运行基准测试以查看最终结果。
改进
第一个罪犯是parseInput，它正在分配n个大小的整数切片，其中n个拼图的输入。代替整数[]int，我们可以使用一个字节[]byte，因此我们可以使用更少的内存
存储相同的信息
（作为奖励，我们跳过从字符串到整数解析）。我们可以这样做，因为难题的约束输入号是从0到8。
如果我们做list parseInput
data := strings.Split(strings.Split(s, "\n")[0], ",")也是我们在此之后投掷的空间，而是通过char更好地解析char。新的变化了parseInput
func parseInput(s string) []byte {
fish := make([]byte, 0, len(s)/2)
for i := 0; i < len(s); i++ {
if s[i] == '\n' {
break
}
if s[i] == ',' {
continue
}
fish = append(fish, s[i])
}
return fish
}
第三个罪犯是tempFish片。在每次迭代中，我们都在填充切片，只是为了抛弃下一步并创建一个新的步骤，并且我们一直在重新整合内存。我们可以通过清除切片而不是创建新的切片来重复使用相同的切片。
Solve函数的新代码
func Solve(input string, days int) int {
fish := parseInput(input)
tempFish := []byte{}
for i := 0; i < days; i++ {
for j := range fish {
if fish[j] == '0' {
fish[j] = '6'
tempFish = append(tempFish, '8')
} else {
fish[j]--
}
}
fish = append(fish, tempFish...)
tempFish = tempFish[:0]
}
return len(fish)
}
结果
重新设计基准
go test . -benchmem -run=^$ -v -bench ^Bench -count=5 -memprofile improved.out | tee improved.txt
和结果
pkg: advent-of-code/2021/go/day-6
BenchmarkSolution
BenchmarkSolution-10 388 2945361 ns/op 2193282 B/op 45 allocs/op
BenchmarkSolution-10 410 2950991 ns/op 2193280 B/op 45 allocs/op
BenchmarkSolution-10 409 2917432 ns/op 2193278 B/op 45 allocs/op
BenchmarkSolution-10 404 2968872 ns/op 2193277 B/op 45 allocs/op
BenchmarkSolution-10 409 2917535 ns/op 2193281 B/op 45 allocs/op
PASS
ok advent-of-code/2021/go/day-6 7.725s
基准已经看起来更好，但是benchstat可以帮助“通过多少”来回答
benchstat naive.txt improved.txt
name old time/op new time/op delta
Solution-10 5.20ms ± 7% 2.94ms ± 1% -43.51% (p=0.008 n=5+5)
name old alloc/op new alloc/op delta
Solution-10 31.7MB ± 0% 2.2MB ± 0% -93.07% (p=0.008 n=5+5)
name old allocs/op new allocs/op delta
Solution-10 1.02k ± 0% 0.04k ± 0% -95.61% (p=0.008 n=5+5)
因此，新解决方案的速度比旧解决方案快43.51％，需要93.07％的内存才能完成相同的工作。
第2部分
在第二部分中，难题正在运行256天。即使有了以前的改进，至少在我的机器上，我也无法得到结果（等待5分钟后，我放弃了）。
是时候更仔细地思考解决方案并使用更有效的算法，因为解决方案是O(days*fish)，并且每次迭代的鱼类数量都会增加。我们需要找到一种方法来保持鱼的数量不变。
拼图的示例输入
3,4,3,1,2,2,1,1 ....
我们知道，一条鱼可以从0到8的计时器，并注意所有具有相同计时器的鱼都“同步”。这意味着我们可以将所有具有相同计时器的鱼分组，然后将O(days*fish)更改为O(days*8)，哪个。等于O(days)。
我们可以通过将键与键从0到8的键来实现这一目标，以指示计时器和值是具有此计时器的鱼的数量，因此以前的输入将变成
{
0: 0,
1: 3,
2: 2,
3: 2,
4: 1,
5: 0,
6: 0,
7: 0,
8: 0
}
和地图的大小将是恒定的，而不管鱼的数量多少。每天我们每组都会增加计时器，而不是一次增加一条鱼。
我们将发现从第1部分和新的调整后代码
保留
func Solve(input string, days int) int {
fish := parseInput(input)
tmpFish := make(map[uint8]int, 9)
for i := 0; i < days; i++ {
resetCount := 0
for k, v := range fish {
if k == 0 {
resetCount += v
} else {
tmpFish[k-1] = v
}
}
tmpFish[8] += resetCount
tmpFish[6] += resetCount
fish, tmpFish = tmpFish, fish
clear(tmpFish)
}
counter := 0
for _, v := range fish {
counter += v
}
return counter
}
func parseInput(s string) map[uint8]int {
fish := make(map[uint8]int, 9)
for i := 0; i < len(s); i++ {
if s[i] == '\n' {
break
}
if s[i] == ',' {
continue
}
fish[s[i]-'0']++
}
return fish
}
结果
该解决方案返回结果，因此仅这是一个积极的结果，并且该基准的基准
pkg: advent-of-code/2021/go/day-6
BenchmarkSolution
BenchmarkSolution-10 34027 33479 ns/op 2373 B/op 85 allocs/op
BenchmarkSolution-10 35720 33435 ns/op 2374 B/op 85 allocs/op
BenchmarkSolution-10 35521 33486 ns/op 2374 B/op 85 allocs/op
BenchmarkSolution-10 35900 33392 ns/op 2373 B/op 85 allocs/op
BenchmarkSolution-10 35878 33553 ns/op 2373 B/op 85 allocs/op
PASS
ok advent-of-code/2021/go/day-6 7.960s
，然后使用以前的解决方案检查benchstat
benchstat improved.txt new_algo.txt
name old time/op new time/op delta
Solution-10 2.94ms ± 1% 0.03ms ± 0% -98.86% (p=0.008 n=5+5)
name old alloc/op new alloc/op delta
Solution-10 2.19MB ± 0% 0.00MB ± 0% -99.89% (p=0.008 n=5+5)
name old allocs/op new allocs/op delta
Solution-10 45.0 ± 0% 85.0 ± 0% +88.89% (p=0.008 n=5+5)
，我们比在提高代码性能高达98.86％的性能和使用99.89％的内存之前的结果更令人印象深刻。
。奖励点
如果我告诉您还有一个单行改进，可以使代码的性能再增加95.90％，并达到零内存分配？
benchstat new_algo.txt new_algo_array.txt
name old time/op new time/op delta
Solution-10 33.5µs ± 0% 1.4µs ± 2% -95.90% (p=0.008 n=5+5)
name old alloc/op new alloc/op delta
Solution-10 2.37kB ± 0% 0.00kB -100.00% (p=0.008 n=5+5)
name old allocs/op new allocs/op delta
Solution-10 85.0 ± 0% 0.0 -100.00% (p=0.008 n=5+5)
您可以尝试将数据结构从map[uint8]int更改为[]int，其余代码仍然可以正常工作。为什么您可能想知道或者您可能已经猜到了，但我将其作为练习，使用分析数据，答案在那里。
提示：您可以使用-cpuprofile而不是-memprofile运行基准，并使用go tool pprof
随时在评论中发布答案ð
结论
这个难题的代码是微不足道的，但是测量，寻找瓶颈，改进代码和重复的方法，直到满足结果，即使在生产设置中也是相同的。学会利用语言和生态系统提供的工具，您不会失望的。
图像上的Gopher艺术来自MariaLetta。