任務

你需要用字典存儲一些鍵和“分數”的映射關系。你經常需要以自然順序(即以分數的升序)訪問鍵和分數值，并能夠根據那個順序檢查一個鍵的排名。對這個問題，用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