Algorithm
740. 删除并获得点数
// nums convert to numMaps
// f(n) = max(f(n-2) + numMaps(n-1) * (n-1),f(n-1))
func deleteAndEarn(nums []int) int {
numMaps := make(map[int]int)
maxNum := 0
for _, num := range nums {
if num > maxNum {
maxNum = num
}
_, ok := numMaps[num]
if ok {
numMaps[num] += 1
}
if !ok {
numMaps[num] = 1
}
}
results := make([]int, maxNum+1)
results[0] = 0
results[1] = numMaps[1]
if maxNum == 1 {
return results[1]
}
results[2] = max(numMaps[1], numMaps[2] * 2)
if maxNum == 2 {
return results[2]
}
for i := 3; i <= maxNum; i++ {
results[i] = max(results[i-2]+numMaps[i] * i, results[i-1])
}
return results[maxNum]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
Review
6 Ways To Boost the Performance of Your Go Applications
- 设置合理的GOMAXPROCS，和CPU核数保持一致效率最高
- 调整struct的field以符合内存对齐的规则，从而来减少内存分配浪费
- 调整GC的GOMEMLIMIT
- 使用unsafe来进行string和byte转换，可以减少内存拷贝
// For Go 1.20 and higher
func StringToBytes(s string) []byte {
return unsafe.Slice(unsafe.StringData(s), len(s))
}
func BytesToString(b []byte) string {
return unsafe.String(unsafe.SliceData(b), len(b))
}
- 使用jsoniter来代替encoding/json
- sync.Pool来重复利用已经分配的内存，来减少GC压力
TIP
分库分表会带来读扩散问题？怎么解决？
Q: 什么是读扩散？
A: 分库分表之后查询条件包含非分片建的话，会导致需要到每个分片库都查一遍，也就引入了读扩散的问题
Q: 怎么解决读扩散？
A: 用普通索引列作分片键建一个新表，先查新表拿到id后再回到原表再查一次原表。这本质上是借鉴了倒排索引的思路。这里可以引入ES，将数据库的内容同步到ES（自带倒排索引）上提供近实时的查询能力。
Share
学习mysql 45讲
38 | 都说InnoDB好， 那还要不要使用Memory引擎？
内存表的数据组织结构
InnoDB和Memory引擎的数据组织方式是不同的：
- InnoDB引擎把数据放在主键索引上， 其他索引上保存的是主键id。 这种方式， 我们称之为索引组织表（IndexOrganizied Table）
- Memory引擎采用的是把数据单独存放， 索引上保存数据位置的数据组织形式， 我们称之为堆组织表（Heap Organizied Table）
这两个引擎的一些典型不同：
- InnoDB表的数据总是有序存放的， 而内存表的数据就是按照写入顺序存放的；
- 当数据文件有空洞的时候， InnoDB表在插入新数据的时候， 为了保证数据有序性， 只能在固定的位置写入新值， 而内存表找到空位就可以插入新值；
- 数据位置发生变化的时候， InnoDB表只需要修改主键索引， 而内存表需要修改所有索引；
- InnoDB表用主键索引查询时需要走一次索引查找， 用普通索引查询的时候， 需要走两次索引查找。而内存表没有这个区别， 所有索引的“地位”都是相同的。
- InnoDB支持变长数据类型， 不同记录的长度可能不同； 内存表不支持Blob 和 Text字段， 并且即使定义了varchar(N)， 实际也当作char(N)， 也就是固定长度字符串来存储， 因此内存表的每行数据长度相同
内存表的缺点
- 内存表不支持行锁， 只支持表锁。 因此， 一张表只要有更新， 就会堵住其他所有在这个表上的读写操作
- 数据库重启的时候， 所有的内存表都会被清空。
39 | 自增主键为什么不是连续的？
自增值保存在哪儿？
- MyISAM引擎的自增值保存在数据文件中。
- InnoDB引擎的自增值， 其实是保存在了内存里， 并且到了MySQL 8.0版本后， 才有了“自增值持久化”的能力（保存在redo log里面）， 也就是才实现了“如果发生重启， 表的自增值可以恢复为MySQL重启前的值”。
可能导致自增主键不连续的原因
- 唯一键冲突是导致自增主键id不连续的第一种原因。
- 事务回滚
- 批量申请主键ID可能导致自增主键不连续
