Algorithm
func uniquePathsWithObstacles(obstacleGrid [][]int) int {
m := len(obstacleGrid)
n := len(obstacleGrid[0])
if obstacleGrid[0][0] == 1 || obstacleGrid[m-1][n-1] == 1 {
return 0
}
results := make([][]int, m)
for i := 0; i < m; i++ {
results[i] = make([]int, n)
}
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if i == 0 && j == 0 {
results[i][j] = 1
continue
}
if j == 0 {
if obstacleGrid[i][j] == 0 {
results[i][j] = results[i-1][j]
} else {
results[i][j] = 0
}
continue
}
if i == 0 {
if obstacleGrid[i][j] == 0 {
results[i][j] = results[i][j-1]
} else {
results[i][j] = 0
}
continue
}
if obstacleGrid[i][j] == 0 {
results[i][j] = results[i][j-1] + results[i-1][j]
} else {
results[i][j] = 0
}
}
}
return results[m-1][n-1]
}
Review
Concurrency in Go: Channels and WaitGroups
TIP
限流的几种实现方式
- 分布式限流，所有机器实例通过对同一个redis key进行incres操作来达到分布式限流的目的。优点是限流操作精准，不会有误限情况。缺点是当限流qps偏高之后，redis的读写将会成为瓶颈。
- 本地限流，设置一个整体限流值/机器实例数，然后将这个平均得到的限流值分发到每个机器实例上，每个机器实例上通过滑动窗口实现本地限流。优点是适合大qps限流场景，操作简单性能好。缺点是容易产生误限（机器实例之间并不能保障完全负载均衡）。
Share
学习“redis设计与实现”
Redis 数据类型
为了让基于类型的操作更加方便地执行，Redis 创建了自己的类型系统。
对象处理机制
- redis对于键所保存的值的类型（后简称“键的类型” ），键能执行的命令又各不相同Redis 必须让每个键都带有类型信息，使得程序可以检查键的类型，并为它选择合适的处理方式。
- Redis 的每一种数据类型，比如字符串、列表、有序集，它们都拥有不只一种底层实现（Redis 内部称之为编码，encoding），所以redis需要根据数据类型的不同编码进行多态处理。
为了解决以上问题，Redis 构建了自己的类型系统，这个系统的主要功能包括：
• redisObject 对象。
• 基于 redisObject 对象的类型检查。
• 基于 redisObject 对象的显式多态函数。
• 对 redisObject 进行分配、共享和销毁的机制。
redisObject 数据结构，以及 Redis 的数据类型
typedef struct redisObject {
// 类型
unsigned type:4;
// 对齐位
unsigned notused:2;
// 编码方式
unsigned encoding:4;
// LRU 时间（相对于 server.lruclock）
unsigned lru:22;
// 引用计数
int refcount;
// 指向对象的值
void *ptr;
} robj;
// type的枚举
#define REDIS_STRING 0 // 字符串
#define REDIS_LIST 1 // 列表
#define REDIS_SET 2 // 集合
#define REDIS_ZSET 3 // 有序集
#define REDIS_HASH 4 // 哈希表
// encoding枚举
#define REDIS_ENCODING_RAW 0 // 编码为字符串
#define REDIS_ENCODING_INT 1 // 编码为整数
#define REDIS_ENCODING_HT 2 // 编码为哈希表
#define REDIS_ENCODING_ZIPMAP 3 // 编码为 zipmap
#define REDIS_ENCODING_LINKEDLIST 4 // 编码为双端链表
#define REDIS_ENCODING_ZIPLIST 5 // 编码为压缩列表
#define REDIS_ENCODING_INTSET 6 // 编码为整数集合
#define REDIS_ENCODING_SKIPLIST 7 // 编码为跳跃表
redis所有的数据类型以及对应的编码类型
命令的类型检查和多态
当执行一个处理数据类型的命令时，Redis 执行以下步骤：
- 根据给定 key ，在数据库字典中查找和它相对应的 redisObject ，如果没找到，就返回NULL 。
- 检查 redisObject 的 type 属性和执行命令所需的类型是否相符，如果不相符，返回类型错误。
- 根据 redisObject 的 encoding 属性所指定的编码，选择合适的操作函数来处理底层的数据结构。
- 返回数据结构的操作结果作为命令的返回值。
对象共享
有一些对象在 Redis 中非常常见，比如命令的返回值 OK 、ERROR 、WRONGTYPE 等字符，另外，一些小范围的整数，比如个位、十位、百位的整数都非常常见。Redis 在内部使用了一个 Flyweight 模式 ：通过预分配一些常见的值对象，并在多个数据结构之间共享这些对象，程序避免了重复分配的麻烦，也节约了一些 CPU时间。个人理解就是一个全局不可变的常量共享，并通过指针到需要的时候获取到相对应的值。
引用计数以及对象的销毁
为了及时对redisObject所占用的内存进行回收，Redis 的对象系统使用了引用计数技术来负责维持和销毁对象（就是自己实现了一套GC），它的运作机制如下：
• 每个 redisObject 结构都带有一个 refcount 属性，指示这个对象被引用了多少次。
• 当新创建一个对象时，它的 refcount 属性被设置为 1 。
• 当对一个对象进行共享时，Redis 将这个对象的 refcount 增一。
• 当使用完一个对象之后，或者取消对共享对象的引用之后，程序将对象的 refcount 减一。
• 当对象的 refcount 降至 0 时，这个 redisObject 结构，以及它所引用的数据结构的内存，都会被释放。
字符串
字符串编码
字符串类型分别使用 REDIS_ENCODING_INT 和 REDIS_ENCODING_RAW 两种编码：
• REDIS_ENCODING_INT 使用 long 类型来保存 long 类型值。
• REDIS_ENCODING_RAW 则使用 sdshdr 结构来保存 sds （也即是 char* )、long long 、double 和 long double 类型值。
换句话来说，在 Redis 中，只有能表示为 long 类型的值，才会以整数的形式保存，其他类型的整数、小数和字符串，都是用 sdshdr 结构来保存。
新创建的字符串默认使用 REDIS_ENCODING_RAW 编码，在将字符串作为键或者值保存进数据库时，程序会尝试将字符串转为 REDIS_ENCODING_INT 编码。
