任務

你想定義一個固定尺寸的緩存，當它被填滿時，新加入的元素會覆蓋第一個(最老的)元素。這種數據結構在存儲日志和歷史信息時非常有用。

解決方案

當緩存填滿時，本節解決方案及時地修改了緩存對象，使其從未填滿的緩存類變成了填滿的緩存類:

class RingBuffer(object):"""這是一個未填滿的緩存類""" def __init__(self,size_max):self.max = size_maxself.data = [ ]class __Full(object):"""這是一個填滿了的緩存類""" def append(self,x):"""加入新的元素覆蓋最舊的元素"""self.data[self.cur] = xself.cur = (self.cur+1) % self.maxdef tolist(self):"""以正確的順序返回元素列表"""return self,data[self.cur:] + self.data[:self.cur]def append(self,x):"""在緩存末尾增加一個元素"""self.data.append(x)if len(self.data) == self.max:self.cur = 0#永久性地將self的類從非滿改成滿self.__class__ = self.__Fulldef tolist(self):"""返回一個從最舊的到最新的元素的列表"""return self.data
#用法示例
if __name__ == '__main__'x = RingBuffer(5)x.append(1);x.append(2);x.append(3);x.append(4)print x.__class__, x.tolist()x.append(5)print x.__class__, x.tolist()x.append(6)print x.data,x.tolist()x.append(7); x.append(8); x.append(9); x.append(10)print x.data,x.tolist()

討論

緩存環是有固定大小的緩存。當它被填滿時，加入新元素會覆蓋掉它持有的最舊的元素。在存儲日志和歷史信息時緩存環是非常有用數據結構。Python并沒有為這種數據結構提供直接支持，但用它構建一個這種結構卻輕而易舉。本節解決方案專門為元素插入進行了優化。

一個值得注意的設計要點是，這些對象在它們的生命周期中會經歷某種不可逆轉的狀態轉變——從未填滿的緩存變成填滿的緩存(從此時開始它的行為方式也發生了變化)，我通過修改 self.__class__ 來完成這個轉變。這種方式對經典類和新風格類都同樣有效，只要這些舊的或者新的類的對象都擁有相同的槽(但對兩個沒有槽的新風格類也有效，比如本節的RingBufer和Full類)。注意，和其他語言不同，雖然Full類的實現位于 RingBufer 類的內部，但兩者并沒有什么特別的聯系，這樣其實很好，因為我們完全不需要這種聯系。

修改類實例在很多語言中會顯得很古怪，但在Python中，相比于其他一些隨意的、無法逆轉的、零散的修改方式，它是一種很好的選擇。而且，這樣的修改對于所有的類都是可行的。
緩存環(或者叫做有界的隊列)是一個很棒的點子，但是總測試緩存環有沒有被填滿是很低效的操作，我們也可以找到別的辦法，但是測試本身就是一件很討厭的事情。這種討厭的事情在 Python 世界中是不受歡迎的，雖然用Python 來做這些事并沒有什么難度，而且測試還涉及了更多的內存使用。關鍵就在于當環被填滿時，給__class__賦值以改變其行為方式，這也是它效率出眾的原因:這種類轉換是一次性的操作，所以它不會帶來任何性能上的開銷。

另一種選擇是，我們可以切換實例的兩個方法而非整個類，來使它變成填滿的狀態:

class RingBuffer(object):def __init__(self,size_max):self.max = size_maxself.data=[]def _full_append(self,x):self.data[self.cur] = xself.cur = (self.cur+1) % self.maxdef _full_get(self):return self.data[self.cur:] + self.data[:self.cur]def append(self,x):self.data.append(x)if len(self.data) == self.max:self.cur = 0#Permanently change self's methods from non-full to fullself.appand = self._full_appendself.tolist = self._full_getdef tolist(self):return self.data

這種切換的方式本質上等價于解決方案給出的類切換方式，盡管具體機制不同。當需要成組地切換所有的方法時，類切換的方式可能是最佳的，而方法切換則在需要更細的行為粒度控制的時候更加合適。當需要在新風格類中切換某些特殊方法時，類切換是唯一的辦法，這是因為它固有的特殊方法查詢是針對類進行的，而不是針對實例的(經典類和新風格類在這個方面截然不同)。

還可以使用其他很多方法來實現緩存環。在Python2.4中，可以考慮從新類型collections.deque 派生一個子類，這個類型提供了“雙頭隊列”，因而從任意一頭添加或者刪除數據的效率都是相當的:

from collections import deque
class RingBuffer(deque):def __init__(self,size_max):deque.__init__(self)self.size_max = size_maxdef append(self,datum):deque.append(self,datum)if len(self) > self.size_max:self.popleft()def tolist(self):return list(self)

或者，當環處于穩定狀態時，為了避免if語句，還可以混用方法切換:

from collections import deque
class RingBuffer(deque):def __init__(self,size_max):deque.__init__(self)self.size_max = size_maxdef _full_append(self,datum):deque.append(self,datum)self.popleft()def append(self,datum):deque.append(self,datum)if len(self) == self.size_max:self.append = self._full_appenddef tolist(self):return list(self)

在最后的這個實現中，我們只需要切換 append 方法(而tolist方法則保持原狀)，在這里方法切換顯得比類切換更方便。