Algorithm
func minimumDeleteSum(s1 string, s2 string) (result int) {
n := len(s1)
m := len(s2)
dp := make([][]int,n+1)
for i := 0; i <= n; i++ {
dp[i] = make([]int,m+1)
}
dp[0][0] = 0
columnSum := 0
for i := 1; i <= m; i++ {
columnSum += int(s2[i-1])
dp[0][i] = columnSum
}
rowSum := 0
for i := 1; i <= n; i++ {
rowSum += int(s1[i-1])
dp[i][0] = rowSum
}
for i := 1; i <= n; i++ {
for j := 1; j <= m; j++ {
if s1[i-1] == s2[j-1] {
dp[i][j] = dp[i-1][j-1]
}else{
dp[i][j] = min(dp[i-1][j] + int(s1[i-1]), dp[i][j-1] + int(s2[j-1]))
}
}
}
return dp[n][m]
}
func min(a,b int)int {
if a <= b {
return a
}
return b
}
Review
Stop testing your code!
文章作者观点是抛弃单元测试,把微服务单做一个unit进行测试,这个观点其实就是现在国内常用的服务集成测试了。我个人持不同观点,就是单元测试的稳定性和解耦性是微服务测试所不具有的。单元测试最重要也是区别于传统手工测试(系统测试)的点,就在于单元测试把外部依赖都给mock了,确保了单元测试的稳定性和性能。把微服务单做unit进行测试,最大的问题就是不稳定和前置准备工作太多。举一个case,有一个接口需要再数据库插入一条具有唯一键的数据,这时候你的测试case很有可能第一次run能通过,第二次就fail了。
TIP
工作过程了解了go里面匿名嵌套结构体的初始化,样例如下:
type AutoGenerated struct {
A struct {
B int `json:"b"`
} `json:"a"`
}
func aaa() {
a1 := AutoGenerated{
A: struct{
B int `json:"b"`
}{B: 1,},
}
}
Share
分享这周学习csapp,看到的比较一个有趣的例子:
// 假设dst和src都为2028的二维数组
func copyij(src [][]int, dst [][]int) {
for i := 0; i < 2048; i++ {
for j := 0; j < 2048; j++ {
dst[i][j] = src[i][j]
}
}
}
func copyji(src [][]int, dst [][]int) {
for j := 0; j < 2048; j++ {
for i := 0; i < 2048; i++ {
dst[i][j] = src[i][j]
}
}
}
上面这2个函数,哪个性能更好呢?
答案是copyij,原因是前者计算机的L1缓存命中率更高。
首先了解2个知识点:
- 计算器CPU L1缓存大小以kb为单位
- 数组在内存里面是连续的内存块。
copyij在进行copy的时候是从二维数组内存块的头开始一直遍历到尾,整个过程基本在L1缓存内完成。而copyji是在多个一维数组之间来回copy,一个2048长度数组基本就塞满L1缓存了,也就导致每执行一次dst[i][j] = src[i][j],L1就要做一次刷新,整个过程性能比copyij差很多。