ARTS #67

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

1. 分批次加载文件内容到内存中

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
  }
}

2. 使用sync.Pool减少gc压力
3. 使用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会使用内部临时表

总结

1. 如果语句执行过程可以一边读数据， 一边直接得到结果， 是不需要额外内存的， 否则就需要额外的内存， 来保存中间结果；
2. join_buffer是无序数组， sort_buffer是有序数组， 临时表是二维表结构；
3. 如果执行逻辑需要用到二维表特性， 就会优先考虑使用临时表。 union需要用到唯一索引约束， group by还需要用到另外一个字段来存累积计数。