Algorithm
152. 乘积最大子数组
func maxProduct(nums []int) int {
maxNums := make([]int, len(nums))
maxNums[0] = nums[0]
minNums := make([]int, len(nums))
minNums[0] = nums[0]
maxNum := maxNums[0]
for i := 1; i < len(nums); i++ {
current := nums[i]
maxNums[i] = max(current, current*minNums[i-1], current*maxNums[i-1])
minNums[i] = min(current, current*minNums[i-1], current*maxNums[i-1])
if maxNums[i] > maxNum {
maxNum = maxNums[i]
}
}
return maxNum
}
func max(a, b, c int) int {
if a > b {
if a > c {
return a
} else {
return c
}
} else {
if b > c {
return b
} else {
return c
}
}
}
func min(a, b, c int) int {
if a < b {
if a < c {
return a
} else {
return c
}
} else {
if b < c {
return b
} else {
return c
}
}
}
Review
Go Panic & Recover: Don’t Make These Mistakes
简单阐述了go里面panic和recover的用法，有一个值得注意的是如果是在协程里面发生panic的话就必须在协程对应的function里面做好defer和recover，在开启协程的地方是没有效果的。
TIP
单调栈结构解决三道算法题
学习了下单调栈
Share
学习mysql 45讲
35 | join语句怎么优化？
Multi-Range Read优化
这个优化的主要目的是尽量使用顺序读盘。因为大多数的数据都是按照主键递增顺序插入得到的， 所以我们可以认为， 如果按照主键的递增顺序查询的话， 对磁盘的读比较接近顺序读， 能够提升读性能。因为MRR的优化就是尽量走到顺序读磁盘的逻辑：
- 根据索引a， 定位到满足条件的记录， 将id值放入read_rnd_buffer中;
- 将read_rnd_buffer中的id进行递增排序；
- 排序后的id数组， 依次到主键id索引中查记录， 并作为结果返回
MRR能够提升性能的核心在于， 这条查询语句在索引a上做的是一个范围查询（也就是说， 这是一个多值查询） ， 可以得到足够多的主键id。 这样通过排序以后， 再去主键索引查数据， 才能体现出“顺序性”的优势。
Batched Key Access
BKA算法， 其实就是对NLJ算法的优化。
NLJ算法执行的逻辑是： 从驱动表t1， 一行行地取出a的值， 再到被驱动表t2去做join。 也就是说， 对于表t2来说， 每次都是匹配一个值。 这时， MRR的优势就用不上了。
那怎么才能一次性地多传些值给表t2呢？ 方法就是， 从表t1里一次性地多拿些行出来， 一起传给表t2。
既然如此， 我们就把表t1的数据取出来一部分， 先放到一个临时内存。 这个临时内存不是别人，就是join_buffer。
BNL算法的性能问题
InnoDB对Bufffer Pool的LRU
算法做了优化， 即： 第一次从磁盘读入内存的数据页， 会先放在old区域。 如果1秒之后这个数据页不再被访问了， 就不会被移动到LRU链表头部， 这样对Buffer Pool的命中率影响就不大。
但是， 如果一个使用BNL算法的join语句， 多次扫描一个冷表， 而且这个语句执行时间超过1秒，就会在再次扫描冷表的时候， 把冷表的数据页移到LRU链表头部。如果这个冷表很大， 就会出现另外一种情况： 业务正常访问的数据页， 没有机会进入young区域。
也就是说， BNL算法对系统的影响主要包括三个方面：
- 可能会多次扫描被驱动表， 占用磁盘IO资源；
- 判断join条件需要执行M*N次对比（M、 N分别是两张表的行数） ， 如果是大表就会占用非常多的CPU资源；
- 可能会导致Buffer Pool的热数据被淘汰， 影响内存命中率。
BNL转BKA
一些情况下， 我们可以直接在被驱动表上建索引， 这时就可以直接转成BKA算法了。但是， 有时候你确实会碰到一些不适合在被驱动表上建索引的情况。
这时候， 我们可以考虑使用临时表。 使用临时表的大致思路是：
- 把表t2中满足条件的数据放在临时表tmp_t中；
- 为了让join使用BKA算法， 给临时表tmp_t的字段b加上索引；
- 让表t1和tmp_t做join操作。
总体来看， 不论是在原表上加索引， 还是用有索引的临时表， 我们的思路都是让join语句能够用上被驱动表上的索引， 来触发BKA算法， 提升查询性能。
扩展-hash join
MySQL目前的版本还不支持hash join， 但你可以配合应用端自己模拟出来， 理论上效果要好于临时表的方案。
36 | 为什么临时表可以重名？
临时表的特性
- 建表语法是create temporarytable …。
- 一个临时表只能被创建它的session访问， 对其他线程不可见。 所以， session A创建的临时表t， 对于session B就是不可见的。
- 临时表可以与普通表同名。
- session A内有同名的临时表和普通表的时候， show create语句， 以及增删改查语句访问的是临时表。
- show tables命令不显示临时表
临时表的应用
可以用于分库分表的跨表查询的数据聚合，各个分库拿到的数据， 汇总到一个MySQL实例的一个表中， 然后在这个汇总实例上做逻辑操作。
为什么临时表可以重名？
MySQL要给InnoDB表创建一个frm文件保存临时表结构定义， 还要有地方保存表数据。这个frm文件放在临时文件目录下， 文件名的后缀是.frm， 前缀是“#sql{进程id}{线程id}序列号”。 因为区分了进程号+线程号，所以可以做到不同session临时表重名。
