撲克小記

場(chǎng)景:三個(gè)人打牌,懷疑少牌。于是清牌,兩人開始正面分類,如果某種花色少
于四張則此花色少牌。我則提議數(shù)總數(shù),少于五十四張就少牌了。

出于專業(yè)的關(guān)系,立馬聯(lián)想到這是個(gè)算法問題。判定是否少牌比少哪張牌需要的信息量少得多。

算法一:判定少哪張牌

kind = new dict(0) #每種花色張數(shù)初始值為0

for c in cards:
    kind[c] += 1

for k,v in kind:
    if v < 4:
        print(k+"缺"+(4 - v)+"張")

時(shí)間復(fù)雜度為O(n),空間復(fù)雜的為O(n)。

算法二:是否少牌

sum(cards)< 54 

如果cards從文件中讀取,時(shí)間復(fù)雜度為O(n),空間復(fù)雜度為O(1)。

還有個(gè)最重要的差距是并行化的難易程度,因?yàn)槲覀冇腥齻€(gè)人,相當(dāng)于三顆CPU。
算法一有一個(gè)共有數(shù)據(jù)kind字典,因此同步數(shù)據(jù)時(shí),有鎖的問題。想要實(shí)現(xiàn)
lock-free,就要各自保存一份kind字典,最后歸總,空間復(fù)雜度和時(shí)間復(fù)雜度
與n成正比。相比之下算法二,天生lock-free很容易實(shí)現(xiàn)并行,并不會(huì)帶來多余
的復(fù)雜度。

提到這個(gè)問題是想說明,問題定義清晰能減少很多無用功。當(dāng)然在這里體現(xiàn)不明
顯,純屬閑的。

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成,瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明:文章內(nèi)容(如有圖片或視頻亦包括在內(nèi))由作者上傳并發(fā)布,文章內(nèi)容僅代表作者本人觀點(diǎn),簡(jiǎn)書系信息發(fā)布平臺(tái),僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容