踩坑记——覆写Python中的__cmp__


最近做一个简单的排行榜功能时,不小心踩到一个Python语言上的坑,花费掉我不少时间才找出具体原因,值得记录一下。


具体功能需求是这样的,制作一个500人的积分排行榜(TOP 500),每个人的积分只增不减,分数相同时比较上榜的时间戳,先达到积分的用户排名靠前。

这种排行榜之前已经做过无数个,一般的,会先抽象出一个TopItem对象,保存用户的积分,以及姓名、UUID等相关信息。然后用一个list对象tops保存有序的500元素,并用一个dict对象cache保存一个uuid到TopItem的映射。由于Python对象的引用特性,多增加一个dict对象,并没有增加TopItem对象的副本,而是均指向同一个TopItem对象,所以内存方面也不会有什么太大的问题。

所以,整个的数据结构大概如下伪代码所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class TopItem(object):
def __init__(self, uuid, name, score, t):
self.uuid = uuid
self.name = name
self.score = score
self.t = t


class TopStub(object):
def __init__(self, tops):
self.tops = copy.deepcopy(tops)
self.cache = {}
for item in self.tops:
if item.uuid not in self.cache:
self.cache[item.uuid] = item

当玩家每次打榜时,先从cache中按照uuid寻找TopItem对象,找不到对象,则直接根据分数,用二分查找的方式进行插入;如果找到对象TopItem,则更新其分数、姓名等信息,然后将其从tops列表中删除,之后再进行二分查找插入(由于分数只增不减,所以这里还有优化的空间)。

这次的排行榜,策划大大要求能够处理同分情况(比较时间戳),于是我很自然的想到覆写TopItem的__cmp__函数,这样就可以直接用<>比较TopItem,后面写代码岂不是美滋滋。于是写出如下的__cmp__函数:

1
2
3
4
5
6
7
8
9
10
11
class TopItem(object):
# see above
def __cmp__(self, other):
if self.score != other.score:
return cmp(self.score, other.score)
else:
return cmp(other.t, self.t)


class TopStub(object):
# see above

测试时我制作了一个测试函数,一次性随机的插入N条随机分数的用户数据,QA也测试通过,没什么问题。

直到上线。

大概2个小时之后,我发现排行榜彻底乱掉,出现一种“分段降序”现象,并且有用户的信息在排行榜中连着出现多次。

可劲一通查,发现问题出在__cmp__和list.remove上面。

从__cmp__的定义中可以看出,如果两个TopItem的score和t均相等,那么我们将判断两个TopItem相等。而list.remove(item)则是删除第一个和item相等的元素。这里对__cmp__进行覆写,显然,影响到对于相等的判断。也就是说,如果两个TopItem的积分和时间戳相等,那么,将有可能在list.remove(item)这一步错误的TopItem,所以才会出现排行榜中同时出现多个同样用户信息的情况。

写个一段代码验证一下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def test():
t1 = TopItem('uuid1', 'aaa', 80, 10)
t2 = TopItem('uuid2', 'bbb', 90, 11)
t3 = TopItem('uuid3', 'ccc', 90, 11)
t4 = TopItem('uuid4', 'ddd', 100, 11)
tops = [t4, t3, t2, t1]
print 'tops:', tops
tops.remove(t2)
print 'after remove t2:bbb'
print 'tops:', tops

output:
tops: [(ddd,100,11), (ccc,90,11), (bbb,90,11), (aaa,80,10)]
after remove t2:bbb
tops: [(ddd,100,11), (bbb,90,11), (aaa,80,10)]

果然没错,我们想删除t2(bbb),但是却把和t2“相等”的t3(ccc)删除了。

那么接下来的修正也很简单:

1
2
3
4
5
6
7
8
9
10
11
12
    def __cmp__(self, other):
if self.score != other.score:
return cmp(self.score, other.score)
elif self.t != other.t:
return cmp(other.t, self.t)
else:
return cmp(id(self), id(other))

run test again and output:
tops: [(ddd,100,11), (ccc,90,11), (bbb,90,11), (aaa,80,10)]
after remove t2:bbb
tops: [(ddd,100,11), (ccc,90,11), (aaa,80,10)]

总结

记得之前看一些Python的文章时,有人说过,对于双下划线开头的这些函数,除非你确切知道自己在干什么,否则不要覆写这些函数。当时我还不以为然:既然Python提供了这么多有意思的钩子,干嘛不用呢?现在我才明白。

另外,覆写__cmp__函数时,在最后一个else分支中,比较id是比较稳妥的做法。

最后,Python3已经废弃掉__cmp__函数,改为提供__eq__, __lt__等多个函数,进一步降低使用者犯错的几率。

推荐阅读:
Python协程:从yield/send到async/await/
探究如何给Python程序做hotfix
从string.strip()引起的一个bug说起

转载请注明出处: http://blog.guoyb.com/2017/09/02/python-cmp/

欢迎使用微信扫描下方二维码,关注我的微信公众号TechTalking,技术·生活·思考:
后端技术小黑屋

评论