ARTS #68

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

1. 设置合理的GOMAXPROCS，和CPU核数保持一致效率最高
2. 调整struct的field以符合内存对齐的规则，从而来减少内存分配浪费
3. 调整GC的GOMEMLIMIT
4. 使用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))
}

5. 使用jsoniter来代替encoding/json
6. 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）

这两个引擎的一些典型不同：

1. InnoDB表的数据总是有序存放的， 而内存表的数据就是按照写入顺序存放的；
2. 当数据文件有空洞的时候， InnoDB表在插入新数据的时候， 为了保证数据有序性， 只能在固定的位置写入新值， 而内存表找到空位就可以插入新值；
3. 数据位置发生变化的时候， InnoDB表只需要修改主键索引， 而内存表需要修改所有索引；
4. InnoDB表用主键索引查询时需要走一次索引查找， 用普通索引查询的时候， 需要走两次索引查找。而内存表没有这个区别， 所有索引的“地位”都是相同的。
5. InnoDB支持变长数据类型， 不同记录的长度可能不同； 内存表不支持Blob 和 Text字段， 并且即使定义了varchar(N)， 实际也当作char(N)， 也就是固定长度字符串来存储， 因此内存表的每行数据长度相同

内存表的缺点

1. 内存表不支持行锁， 只支持表锁。 因此， 一张表只要有更新， 就会堵住其他所有在这个表上的读写操作
2. 数据库重启的时候， 所有的内存表都会被清空。

39 | 自增主键为什么不是连续的？

自增值保存在哪儿？

• MyISAM引擎的自增值保存在数据文件中。
• InnoDB引擎的自增值， 其实是保存在了内存里， 并且到了MySQL 8.0版本后， 才有了“自增值持久化”的能力（保存在redo log里面）， 也就是才实现了“如果发生重启， 表的自增值可以恢复为MySQL重启前的值”。

可能导致自增主键不连续的原因

1. 唯一键冲突是导致自增主键id不连续的第一种原因。
2. 事务回滚
3. 批量申请主键ID可能导致自增主键不连续