Algorithm
740. 刪除并獲得點(diǎn)數(shù)
// 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
- 設(shè)置合理的GOMAXPROCS箫章，和CPU核數(shù)保持一致效率最高
- 調(diào)整struct的field以符合內(nèi)存對齊的規(guī)則，從而來減少內(nèi)存分配浪費(fèi)
- 調(diào)整GC的GOMEMLIMIT
- 使用unsafe來進(jìn)行string和byte轉(zhuǎn)換镜会，可以減少內(nèi)存拷貝
// 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))
}
- 使用jsoniter來代替encoding/json
- sync.Pool來重復(fù)利用已經(jīng)分配的內(nèi)存檬寂，來減少GC壓力
TIP
分庫分表會(huì)帶來讀擴(kuò)散問題？怎么解決戳表？
Q: 什么是讀擴(kuò)散桶至？
A: 分庫分表之后查詢條件包含非分片建的話，會(huì)導(dǎo)致需要到每個(gè)分片庫都查一遍匾旭，也就引入了讀擴(kuò)散的問題
Q: 怎么解決讀擴(kuò)散镣屹？
A: 用普通索引列作分片鍵建一個(gè)新表，先查新表拿到id后再回到原表再查一次原表价涝。這本質(zhì)上是借鑒了倒排索引的思路野瘦。這里可以引入ES，將數(shù)據(jù)庫的內(nèi)容同步到ES（自帶倒排索引）上提供近實(shí)時(shí)的查詢能力飒泻。
Share
學(xué)習(xí)mysql 45講
38 | 都說InnoDB好鞭光， 那還要不要使用Memory引擎？
內(nèi)存表的數(shù)據(jù)組織結(jié)構(gòu)
InnoDB和Memory引擎的數(shù)據(jù)組織方式是不同的：
- InnoDB引擎把數(shù)據(jù)放在主鍵索引上泞遗， 其他索引上保存的是主鍵id惰许。 這種方式， 我們稱之為索引組織表（IndexOrganizied Table）
- Memory引擎采用的是把數(shù)據(jù)單獨(dú)存放史辙， 索引上保存數(shù)據(jù)位置的數(shù)據(jù)組織形式汹买， 我們稱之為堆組織表（Heap Organizied Table）
這兩個(gè)引擎的一些典型不同：
- InnoDB表的數(shù)據(jù)總是有序存放的， 而內(nèi)存表的數(shù)據(jù)就是按照寫入順序存放的聊倔；
- 當(dāng)數(shù)據(jù)文件有空洞的時(shí)候晦毙， InnoDB表在插入新數(shù)據(jù)的時(shí)候， 為了保證數(shù)據(jù)有序性耙蔑， 只能在固定的位置寫入新值见妒， 而內(nèi)存表找到空位就可以插入新值；
- 數(shù)據(jù)位置發(fā)生變化的時(shí)候甸陌， InnoDB表只需要修改主鍵索引须揣， 而內(nèi)存表需要修改所有索引；
- InnoDB表用主鍵索引查詢時(shí)需要走一次索引查找钱豁， 用普通索引查詢的時(shí)候耻卡， 需要走兩次索引查找。而內(nèi)存表沒有這個(gè)區(qū)別牲尺， 所有索引的“地位”都是相同的卵酪。
- InnoDB支持變長數(shù)據(jù)類型， 不同記錄的長度可能不同； 內(nèi)存表不支持Blob 和 Text字段溃卡， 并且即使定義了varchar(N)溢豆， 實(shí)際也當(dāng)作char(N)， 也就是固定長度字符串來存儲(chǔ)塑煎， 因此內(nèi)存表的每行數(shù)據(jù)長度相同
內(nèi)存表的缺點(diǎn)
- 內(nèi)存表不支持行鎖， 只支持表鎖臭蚁。 因此最铁， 一張表只要有更新， 就會(huì)堵住其他所有在這個(gè)表上的讀寫操作
- 數(shù)據(jù)庫重啟的時(shí)候垮兑， 所有的內(nèi)存表都會(huì)被清空冷尉。
39 | 自增主鍵為什么不是連續(xù)的？
自增值保存在哪兒系枪？
- MyISAM引擎的自增值保存在數(shù)據(jù)文件中雀哨。
- InnoDB引擎的自增值， 其實(shí)是保存在了內(nèi)存里私爷， 并且到了MySQL 8.0版本后雾棺， 才有了“自增值持久化”的能力（保存在redo log里面）， 也就是才實(shí)現(xiàn)了“如果發(fā)生重啟衬浑， 表的自增值可以恢復(fù)為MySQL重啟前的值”捌浩。
可能導(dǎo)致自增主鍵不連續(xù)的原因
- 唯一鍵沖突是導(dǎo)致自增主鍵id不連續(xù)的第一種原因。
- 事務(wù)回滾
- 批量申請主鍵ID可能導(dǎo)致自增主鍵不連續(xù)
