场景:三个人打牌,怀疑少牌。于是清牌,两人开始正面分类,如果某种花色少
于四张则此花色少牌。我则提议数总数,少于五十四张就少牌了。
出于专业的关系,立马联想到这是个算法问题。判定是否少牌比少哪张牌需要的信息量少得多。
算法一:判定少哪张牌
kind = new dict(0) #每种花色张数初始值为0
for c in cards:
kind[c] += 1
for k,v in kind:
if v < 4:
print(k+"缺"+(4 - v)+"张")
时间复杂度为O(n),空间复杂的为O(n)。
算法二:是否少牌
sum(cards)< 54
如果cards从文件中读取,时间复杂度为O(n),空间复杂度为O(1)。
还有个最重要的差距是并行化的难易程度,因为我们有三个人,相当于三颗CPU。
算法一有一个共有数据kind字典,因此同步数据时,有锁的问题。想要实现
lock-free,就要各自保存一份kind字典,最后归总,空间复杂度和时间复杂度
与n成正比。相比之下算法二,天生lock-free很容易实现并行,并不会带来多余
的复杂度。
提到这个问题是想说明,问题定义清晰能减少很多无用功。当然在这里体现不明
显,纯属闲的。