Algorithm
198. 打家劫舍
// f(n) = max(f(n-2)+nums[n], f(n-3)+nums[n-1])
func rob1(nums []int) int {
length := len(nums)
results := make([]int, length+1)
results[0] = 0
results[1] = nums[0]
if length == 1 {
return results[1]
}
results[2] = max(nums[0], nums[1])
if length == 2 {
return results[2]
}
results[3] = max(results[1] + nums[2],nums[1])
if length == 3 {
return results[3]
}
results[4] = max(results[2] + nums[3],results[1] + nums[2])
if length == 4 {
return results[4]
}
for i := 5; i <= length; i++ {
results[i] = max(results[i-2]+nums[i-1], results[i-3]+nums[i-2])
}
return results[length]
}
// f(n) = max(f(n-2)+nums[n], f(n-1))
func rob(nums []int) int {
length := len(nums)
results := make([]int, length)
results[0] = 0
results[1] = nums[0]
if length == 1 {
return results[1]
}
results[2] = max(nums[0], nums[1])
if length == 2 {
return results[2]
}
for i := 3; i < length; i++ {
results[i] = max(results[i-2]+nums[i], results[i-1])
}
return results[length-1]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
Review
Reading 16GB File in Seconds, Golang
- 分批次加载文件内容到内存中
r := bufio.NewReader(f)
for {
buf := make([]byte,4*1024) //the chunk size
n, err := r.Read(buf) //loading chunk into buffer
buf = buf[:n]
if n == 0 {
if err != nil {
fmt.Println(err)
break
}
if err == io.EOF {
break
}
return err
}
}
- 使用sync.Pool减少gc压力
- 使用goroutine并行处理文件内容，提高效率
TIP
group by可以使用索引，但是优先级在where条件之后。比如下面这个sql
select a from table1 where b = 1 group by c
建议添加联合索引为index_b_c_a(b, c, a)， 联合索引里面的c可以减少filesort的耗时，而a可以减少回表的耗时和IO。
Share
学习mysql 45讲
37 | 什么时候会使用内部临时表？
union 执行流程
union语法需要对数据结果进行去重，所以mysql会使用内部临时表。
group by 执行流程
group by过程需要对数据结果进行排序，所以mysql会使用内部临时表
总结
- 如果语句执行过程可以一边读数据， 一边直接得到结果， 是不需要额外内存的， 否则就需要额外的内存， 来保存中间结果；
- join_buffer是无序数组， sort_buffer是有序数组， 临时表是二维表结构；
- 如果执行逻辑需要用到二维表特性， 就会优先考虑使用临时表。 union需要用到唯一索引约束， group by还需要用到另外一个字段来存累积计数。
