当前位置：首页 > news >正文

Python Cookbook-5.14 给字典类型增加排名功能

news 来源：原创 2025/9/12 9:52:17

任务

你需要用字典存储一些键和“分数”的映射关系。你经常需要以自然顺序(即以分数的升序)访问键和分数值，并能够根据那个顺序检查一个键的排名。对这个问题，用dict 似乎不太合适。

解决方案

我们可以使用 dict 的子类，根据需要增加或者重写一些方法。在我们使用多继承、将UserDict.DictMixin 放置在基类 dict、并仔细安排各种方法的委托或重写之前，我们可以设法获得一种美妙的平衡，既拥有极好的性能又避免了编写一些冗余代码。

我们可以在文档字符串中加入很多示例，还可以用标准库的 doctest 模块来提供单元测试的功能，这也能够确保我们在文档字符串中编写的例子的准确性:

#!/usr/bin/env python
'''一个反映键到分数的映射的字典'''
from bisect import bisect_left,insort_left
import UserDict
class Ratings(UserDict.DictMixin,dict):'''Ratings类很像一个字典，但有一些额外特性:每个键的对应值都是该键的“分数”，所有键都根据它们的分数排名。对应值必须是可以比较的，同样，键则必须是可哈希的(即可以“绑”在分数上)所有关于映射的行为都如同预期一样，比如:>>>r = Ratings({"bob":30,"john":30})>>>len(r)2>>>r.has_key("paul"),"paul" in r(False,False)>>>r["john"] = 20r.update({"paul":20,"tom":10})>>>len(r)4>>>r.has_key("paul"),"paul" in r(True,True)>>>[r[key} for key in ["bob","paul","john","tom"]][30,20,20,10]>>>r.get("nobody"),r.get("nobody",0)(None,0)除了映射的接口，我们还提供了和排名相关的方法。r.rating(key)返回了某个键的排名，其中排名为0的是最低的分数(如果两个键的分数相同，则直接比较它们两者，“打破僵局”，较小的键排名更低):>>>[r.rating(key) for key in ["bob","paul","john","tom"]][3,2,1,0]getValueByRating(ranking)和getKeyByRating(ranking)对于给定的排名索引,分别返回分数和键:>>>[r.getValueByRating(rating) for rating in range(4)][10,20,20,30]>>>[r.getKeyByRating(rating) for rating in range(4)]['tom','john','paul','bob']一个重要的特性是keys()返回的键是以排名的升序排列的,而其他所有返回的相关的列表或迭代器都遵循这个顺序:>>> r.keys()['tom','john','paul','bob']>>>[key for key in r]['tom','john','paul','bob']>>> [key for key in r.iterkeys()]['tom','john','paul','bob']>>> r.values()[10,20,20,30]>>>[value for value in r.itervalues()][10,20,20,30]>>> r.items()[('tom',10),('john',20),('paul',20),('bob',30)]>>>[item for item in r.iteritems()][('tom',10),('john',20),('paul',20),('bob',30)]实例可以被修改(添加、改变和删除键-分数对应关系)而且实例的每个方法都反映了实例的当前状态:>>>r["tom"] = 100>>> r.items()[('john',20),('paul',20),('bob',30),('tom',100)]>>>del r["paul"]>>>r.items()[('john',20),('bob',30),('tom',100)]>>>r["paul"] = 25>>>r.items()[('john',20),('paul',25),('bob',30),('tom',100)]>>>r.clear()>>>r.items()[  ]''''''这个实现小心翼翼地混合了继承和托管，因此在尽量减少冗余代码的前提下获得了不错的性能，当然，同时也保证了语义的正确性。所有未被实现的映射方法都通过继承来获得，大多来自DictMixin，但关键的__getitem__来自 dict。'''def init(self,*args,**kwds):'''这个类就像dict一样被实例化'''dict.__init__(self,*args,**kwds)#self._rating是关键的辅助数据结构:一个所有(值,键)#的列表,并保有一种“自然的”排序状态self._rating =[ (v,k) for k,v in dict.iteritems(self)]self._rating.sort()def copy(self):'''提供一个完全相同但独立的拷贝'''return Ratings(self)def __setitem__(self,k,y):'''除了把主要任务委托给dict，我们还维护self._rating'''if k in self:del self._rating[self.rating(k)]dict.__setitem__(self,k,v)insort_left(self._rating,(v,k))def __delitem__(self，k):'''除了把主要任务委托给dict,我们还维护self._rating'''del self._rating[self.rating(k)]dict.__delitem__(self,k)'''显式地将某些方法委托给dict的对应方法，以免继承了DictMixin的较慢的(虽然功能正确)实现'''__len__ = dict.__len____contains__ = dict.__contains__has_key = __contains__'''在self._rating和self.keys()之间的关键的语义联系————DictMixin“免费”给了我们所有其他方法，虽然我们直接实现它们能够获得稍好一点的性能。'''def __iter__(self):for v,k in self._rating:yield kiterkeys = __iter__def keys(self):return list(self)'''三个和排名相关的方法'''def rating(self,key):item = self[key],keyi = bisect_left(self._rating,item)if item == self._rating[i]:return iraise LookupError,"item not found in rating"def getValueByRating(self,rating):return self._rating[rating][0]def getKeyByRating(self,rating):return self.rating[rating][1]
def _test():'''我们使用doctest来测试这个模块，模块名必须为rating.py，这样docstring中的示例才会有效'''import doctest,ratingdoctest.testmod(rating)
if __name__ == "__main__":_test()

讨论

在很多方面，字典都是很自然地被应用于存储键(比如，竞赛中参与者的名字)和“分数”(比如参与者获得的分数，或者参与者在拍卖中的出价)的对应关系的数据结构。如果我们希望在这些应用中使用字典，我们可能会希望以自然的顺序访间–即键对应的“分数”的升序——我们也希望能够迅速获得基于当前分数的排名(比如，参与者现在排在第三位，排在第二位的参与者的分数，等等)。

为了达到这个目的，本节给dict的子类增加了一些它本身完全不具备的功能(rating方法、getValueByRating、getKeyByRating)，同时，最关键和巧妙的地方是，我们修改了keys方法和其他相关的方法，这样它们就能返回按照指定顺序排列的列表或者可选代对象(比如按照分数的升序排列，对于两个有同样分数的键，我们继续比较键本身)。大多数的文档都放在类的文档字符串中——保留文档和示例是很重要的，可以用Python 标准库的 doctest模块来提供单元测试的功能，以确保给出的例子是正确的。

关于这个实现的有趣之处是，它很关心消除冗余(即那些重复和令人厌烦的代码，很可能滋生 bug)，但同时没有损害性能。Ratings 类同时从 dict 和 DictMixin 继承，并把后者排在基类列表的第一位，因此，除非明确地覆盖了基类的方法，Ratings 的方法基本来自于 DictMixin，如果它提供了的话。

Raymond Hettinger 的 DictMixin 类最初是发布在 Python Cookbook 在线版本中的一个例子，后来被吸收到了 Python2.3的标准库中。DictMixin 提供了各种映射的方法，除了__init__
、copy以及四个基本方法:__getitem__、__setitem__、__delitem__和 keys。如果需要的是一个映射类并且想要支持完整映射所具有的各种方法，可以从DictMixin派生子类，并且提供那些基本的方法(具体依赖于你的类的语义————比如，如果你的类有不可修改的实例，你无须提供属性设置方法__setitem__和__delitem__)。还可以添加一些可选的方法以提升性能，覆盖 DictMixin 所提供的原有方法。整个 DictMixin 的架构可以被看做是一个经典的模板方法设计模式(Template Method Design Pattern)，它用一种混合的变体提供了广泛的适用性。

在本节的类中，从基类继承了__getitem__(准确地说，是从内建的dict类型继承)，出于性能上的考虑，我们把能委托的都委托给了dict。我们必须自己实现基本的属性设置方法(__setitem__和__delitem__)，因为除了委托给基类的方法，还需要维护一个数据结构 self._rating——这是一个列表，包含了许多(score,key)值对，此列表在标准库模块 bisect 的帮助下完成了排序。我们也重新实现了keys(在这个步骤中，还重新实现了__iter__，即 iterkeys，很明显，借助__iter__可以更容易地实现 keys)来利用self._rating 并按照我们需要的顺序返回键。最后，除了上面三个和排名有关的方法，我们又为__init__和 copy 添加了实现。

这个结果是一个很有趣的例子，它取得了简洁和清晰的平衡，并最大化地重用了 Python标准库的众多功能。如果你在应用程序中使用这个模块，测试结果可能会显示，本节的类从 DictMixin 继承来的方法的性能不是太让人满意，毕竞 DictMixin 的实现是基于必要的通用性的考虑。如果它的性能不能满足你的要求，可以自己提供一个实现来获取最高性能。假设有个Ratings类的实例r，你的应用程序需要对r.iteritems()的结果进行大量的循环处理，可以给类的主体部分增加这个方法的实现以获得更好的性能:

def iteritems(self):for v,k in self._rating:yield k,v

任务

解决方案

讨论

相关文章：