場(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)不明
顯,純屬閑的。