0x00 問題來由
最近在做一個斗地主網(wǎng)游的AI。由于斗地主這種游戲，同樣數(shù)字不同花式的牌是等效的，所以，很多計算我們不需要知道具體是哪幾張牌，只需要關(guān)心每種牌有多少張。
于是，我引入了一個數(shù)據(jù)結(jié)構(gòu)，姑且叫做CardsVector，表示每種牌的數(shù)量。為了方便描述，本文約定以下方式來表示一個CardsVector，與具體實現(xiàn)無關(guān)
X = {3:3, 4:2} // X為一個CardsVector，包含3張3，2張4
其中，X[3] == 3, X[4] == 2
這種數(shù)據(jù)結(jié)構(gòu)除了初始化，還有兩個主要的操作：
- 計算一個CardsVector是否包含另一個CardsVector。場景為判斷某種出牌組合在不在當(dāng)前手牌中。比如:
設(shè)A={3:2, 4:2, 5:2}，X={3:1, 4:1, 5:1}，Y={4:3,5:3}，Z={4:1, 5:1, 6:1}
那么，A包含A、X，不包含Y、Z
- 從一個CardsVector中，減去一個CardsVector。場景為出牌后從手牌中移除出掉的牌，如：
設(shè)A={3:2, 4:2, 5:2}，X={3:1, 4:1}，A移除X后為{3:1, 4:1, 5:2}
0x01 初步方案
一開始，我是這樣定義CardsVector的：
type CardsVector [16]int
很簡單粗暴，用一個16個元素的int數(shù)組來保存，每個元素的值表示下標(biāo)對應(yīng)的牌的數(shù)量?！芭袛喟焙汀耙瞥彼惴ㄈ缦拢?/p>
// Contains 判斷包含
func (v CardsVector) Contains(other CardsVector) bool {
for i := 1; i < 16; i++ {
if v[i] < other[i] {
return false
}
}
return true
}
// Remove 移除
func (v CardsVector) Remove(other CardsVector) (res CardsVector) {
for i := 1; i < 16; i++ {
res[i] = v[i] - other[i]
}
}
嗯，簡單粗暴，性能湊合。如果是一般場合，也就這樣算了。可是，對這個數(shù)據(jù)結(jié)構(gòu)的操作，在我寫的棋牌AI中，屬于最高頻的調(diào)用，優(yōu)化性能收益非常大。所以，身為強(qiáng)迫癥患者的我決定進(jìn)一步壓榨性能
0x02 第一次優(yōu)化
根據(jù)我們的需求，總共只有15種牌（A/2/3/4/5/6/7/8/9/10/J/Q/K/小王/大王），不會多也不會少。很多大牛說過，for循環(huán)展開有助提高性能。姑且試試。
但有沒有性能優(yōu)化，還是要拉出來溜溜看。于是啪啪啪的寫unittest，go test之
go test -bench=.VecContains.
BenchmarkVecContainsUsingForLoop-2 20000000 73.9 ns/op
BenchmarkVecContainsNoForLoop-2 100000000 34.0 ns/op
go test -bench=.VecRemove.
BenchmarkVecRemoveUsingForLoop-2 20000000 82.7 ns/op
BenchmarkVecRemoveNoForLoop-2 20000000 57.3 ns/op
不錯不錯，有了大幅提升！但，還能不能更好呢？
0x03 不屈不撓的折騰
其實，以我個人性格，如果只提升1倍左右的話，我是懶得專門寫文章記錄的
注意到這么一點：我們的場景是記錄每種牌的數(shù)量。一副撲克牌中，每種數(shù)字的牌，最多只有4張。上面的數(shù)據(jù)結(jié)構(gòu)，簡單粗暴的用一個[]int來保存。我們能否從這方面入手優(yōu)化呢？
用[]int8的方案我自己先否決了。一個int剛好就是cpu一個字長，處理速度會更快些，即使在不同環(huán)境，cpu緩存等不確定因素可能有影響，也不會有太大的提升。
重要事情再默念三遍——每種最多只有4張！每種最多只有4張！每種最多只有4張！。
也就是說，我們可以只用3個位來表示一種牌的數(shù)量。3X16=48，貌似一個uint64能解決問題。
但，能表示數(shù)據(jù)只是一個前提，這個數(shù)據(jù)結(jié)構(gòu)是否可用，還取決于能否實現(xiàn)上面兩個關(guān)鍵操作。而如果每張牌的數(shù)據(jù)單獨通過連串位運算單獨提取出來，重復(fù)上面的算法，固然是能實現(xiàn)功能的。但這么繁瑣的操作，必定令性能大打折扣。這不符合我們的初衷。于是，我們的思路就去到，通過神器的位運算，實現(xiàn)多個位的同時操作
- 判斷包含
對于問題的描述，我們可以給出以下的等價表達(dá)
a) A包含B
b) 對于任意一種牌x，A[x] >= B[x]
c) 對于任意牌x，有A[x]-B[x] >= 0
對于一個k進(jìn)制多位數(shù)的減法，我們可以表示為（打公式無能，僅用一個4位數(shù)示意）：
A = a3*k^3+a2*k^2+a1*k^1+a0*k^0 (任意0 <= ax < k)
B = b3*k^3+b2*k^2+b1*k^1+b0*k^0 (任意0 <= bx < k)
A-B=(a3-b3)*k^3+(a2-b2)*k^2+(a1-b1)*k^1+(a0-b0)*k^0
設(shè) cx = ax - bx
當(dāng)任意ax>=bx時，A-B可以表示為“c3 c2 c1 c0”這個4位k進(jìn)展數(shù)
回到我們的上文的設(shè)定，我們一個CardsVector用一個48位uint表示，我們可以視為一個16位的8進(jìn)制數(shù)。但這樣，我們拿兩個不確定包含關(guān)系的CardsVector進(jìn)行比較時，無法保證任意ax>=bx，相減后的結(jié)果無法判斷是否符合要求
好吧，我們做一個修正（此處跳過各種不靠譜的草稿本嘗試），我們用4位表示一種牌的數(shù)量。4X15=60，仍然能用一個uint64表示。這時候，每種牌數(shù)量二進(jìn)制的最高位，必然是0的。然后，我們對上面描述c進(jìn)一步轉(zhuǎn)化：
d) 對任意牌x，有A[x] + C - B[x] >= C (C為任一常數(shù))
我們在對兩個A和B這兩個CardsVector相減前，先將A中每種牌的數(shù)量最高位置為1，相當(dāng)于加8。由于原本每種牌最多只有4張，所以必然有A[x]+8>B[x]。但如果A[x]<B[x]，則有0 < A[x]+8-B[x] < 8?；氐轿贿\算中，只需要判斷:
((A[x] | 0x08) - B[x]) & 0x08 == 0x08
說到這里，我們的Contains函數(shù)就呼之欲出了
type CardsVector uint64
const mask CardsVector = 0x8888888888888888 // 多么吉利的數(shù)字
func (v CardsVector ) Contains(other CardsVector ) bool {
return ((v | mask) - other) & mask == mask
}
- 移除
有了上述的推斷，在保證A包含B的前提下，A移除B，就剛好等于A-B了，代碼就懶得寫了
看起來萬事俱備，只欠bench了。不廢話，來
go test -bench=.Contains
BenchmarkVecContainsUsingForLoop-2 20000000 64.3 ns/op
BenchmarkVecContainsNoForLoop-2 30000000 44.5 ns/op
BenchmarkVecBContains-2 2000000000 1.09 ns/op
go test -bench=.Remove
BenchmarkVecRemoveUsingForLoop-2 20000000 92.8 ns/op
BenchmarkVecRemoveNoForLoop-2 100000000 63.9 ns/op
BenchmarkVecBRemove-2 2000000000 1.15 ns/op
0x04 結(jié)論
我覺得我不需要說什么了
