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
限流的幾種實現(xiàn)方式
- 分布式限流奥此，所有機器實例通過對同一個redis key進行incres操作來達(dá)到分布式限流的目的。優(yōu)點是限流操作精準(zhǔn)雁比，不會有誤限情況稚虎。缺點是當(dāng)限流qps偏高之后，redis的讀寫將會成為瓶頸偎捎。
- 本地限流蠢终，設(shè)置一個整體限流值/機器實例數(shù)，然后將這個平均得到的限流值分發(fā)到每個機器實例上茴她，每個機器實例上通過滑動窗口實現(xiàn)本地限流寻拂。優(yōu)點是適合大qps限流場景，操作簡單性能好丈牢。缺點是容易產(chǎn)生誤限（機器實例之間并不能保障完全負(fù)載均衡）祭钉。
Share
學(xué)習(xí)“redis設(shè)計與實現(xiàn)”
Redis 數(shù)據(jù)類型
為了讓基于類型的操作更加方便地執(zhí)行，Redis 創(chuàng)建了自己的類型系統(tǒng)己沛。
對象處理機制
- redis對于鍵所保存的值的類型（后簡稱“鍵的類型” ）慌核，鍵能執(zhí)行的命令又各不相同Redis 必須讓每個鍵都帶有類型信息帕识，使得程序可以檢查鍵的類型，并為它選擇合適的處理方式遂铡。
- Redis 的每一種數(shù)據(jù)類型肮疗，比如字符串、列表扒接、有序集伪货，它們都擁有不只一種底層實現(xiàn)（Redis 內(nèi)部稱之為編碼，encoding）钾怔，所以redis需要根據(jù)數(shù)據(jù)類型的不同編碼進行多態(tài)處理碱呼。
為了解決以上問題，Redis 構(gòu)建了自己的類型系統(tǒng)宗侦，這個系統(tǒng)的主要功能包括：
? redisObject 對象愚臀。
? 基于 redisObject 對象的類型檢查。
? 基于 redisObject 對象的顯式多態(tài)函數(shù)矾利。
? 對 redisObject 進行分配姑裂、共享和銷毀的機制。
redisObject 數(shù)據(jù)結(jié)構(gòu)男旗，以及 Redis 的數(shù)據(jù)類型
typedef struct redisObject {
// 類型
unsigned type:4;
// 對齊位
unsigned notused:2;
// 編碼方式
unsigned encoding:4;
// LRU 時間（相對于 server.lruclock）
unsigned lru:22;
// 引用計數(shù)
int refcount;
// 指向?qū)ο蟮闹? 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 // 編碼為整數(shù)
#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 // 編碼為整數(shù)集合
#define REDIS_ENCODING_SKIPLIST 7 // 編碼為跳躍表
redis所有的數(shù)據(jù)類型以及對應(yīng)的編碼類型
命令的類型檢查和多態(tài)
當(dāng)執(zhí)行一個處理數(shù)據(jù)類型的命令時舶斧，Redis 執(zhí)行以下步驟：
- 根據(jù)給定 key ，在數(shù)據(jù)庫字典中查找和它相對應(yīng)的 redisObject 察皇，如果沒找到茴厉，就返回NULL 。
- 檢查 redisObject 的 type 屬性和執(zhí)行命令所需的類型是否相符什荣，如果不相符矾缓，返回類型錯誤。
- 根據(jù) redisObject 的 encoding 屬性所指定的編碼稻爬，選擇合適的操作函數(shù)來處理底層的數(shù)據(jù)結(jié)構(gòu)嗜闻。
- 返回數(shù)據(jù)結(jié)構(gòu)的操作結(jié)果作為命令的返回值。
對象共享
有一些對象在 Redis 中非常常見因篇，比如命令的返回值 OK 泞辐、ERROR 、WRONGTYPE 等字符竞滓，另外咐吼，一些小范圍的整數(shù)，比如個位商佑、十位锯茄、百位的整數(shù)都非常常見。Redis 在內(nèi)部使用了一個 Flyweight 模式 ：通過預(yù)分配一些常見的值對象，并在多個數(shù)據(jù)結(jié)構(gòu)之間共享這些對象肌幽，程序避免了重復(fù)分配的麻煩晚碾，也節(jié)約了一些 CPU時間。個人理解就是一個全局不可變的常量共享喂急，并通過指針到需要的時候獲取到相對應(yīng)的值格嘁。
引用計數(shù)以及對象的銷毀
為了及時對redisObject所占用的內(nèi)存進行回收，Redis 的對象系統(tǒng)使用了引用計數(shù)技術(shù)來負(fù)責(zé)維持和銷毀對象（就是自己實現(xiàn)了一套GC）廊移，它的運作機制如下：
? 每個 redisObject 結(jié)構(gòu)都帶有一個 refcount 屬性糕簿，指示這個對象被引用了多少次。
? 當(dāng)新創(chuàng)建一個對象時狡孔，它的 refcount 屬性被設(shè)置為 1 懂诗。
? 當(dāng)對一個對象進行共享時，Redis 將這個對象的 refcount 增一苗膝。
? 當(dāng)使用完一個對象之后殃恒，或者取消對共享對象的引用之后，程序?qū)ο蟮?refcount 減一辱揭。
? 當(dāng)對象的 refcount 降至 0 時离唐，這個 redisObject 結(jié)構(gòu)，以及它所引用的數(shù)據(jù)結(jié)構(gòu)的內(nèi)存界阁，都會被釋放侯繁。
字符串
字符串編碼
字符串類型分別使用 REDIS_ENCODING_INT 和 REDIS_ENCODING_RAW 兩種編碼：
? REDIS_ENCODING_INT 使用 long 類型來保存 long 類型值胖喳。
? REDIS_ENCODING_RAW 則使用 sdshdr 結(jié)構(gòu)來保存 sds （也即是 char* )泡躯、long long 、double 和 long double 類型值丽焊。
換句話來說较剃，在 Redis 中，只有能表示為 long 類型的值技健，才會以整數(shù)的形式保存写穴，其他類型的整數(shù)、小數(shù)和字符串雌贱，都是用 sdshdr 結(jié)構(gòu)來保存啊送。
新創(chuàng)建的字符串默認(rèn)使用 REDIS_ENCODING_RAW 編碼，在將字符串作為鍵或者值保存進數(shù)據(jù)庫時欣孤，程序會嘗試將字符串轉(zhuǎn)為 REDIS_ENCODING_INT 編碼馋没。
