扑克小记

场景:三个人打牌,怀疑少牌。于是清牌,两人开始正面分类,如果某种花色少
于四张则此花色少牌。我则提议数总数,少于五十四张就少牌了。

出于专业的关系,立马联想到这是个算法问题。判定是否少牌比少哪张牌需要的信息量少得多。

算法一:判定少哪张牌

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很容易实现并行,并不会带来多余
的复杂度。

提到这个问题是想说明,问题定义清晰能减少很多无用功。当然在这里体现不明
显,纯属闲的。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容