环形缓冲区(circular buffer),也叫循环缓冲区或环形缓冲区,是一种数据结构。它使用单个固定大小的缓冲区,就好像这个缓冲区的首尾是相连的。
环形缓冲区一开始是空的,长度是预先设定好的。 例如,下面是一个包含 7 个元素的缓冲区:
[ ][ ][ ][ ][ ][ ][ ]
假设在缓冲区的中间写入一个 1(在环形缓冲区中,具体的起始位置并不重要):
[ ][ ][ ][1][ ][ ][ ]
然后假设再加入两个元素,2 和 3,它们会被追加到 1 的后面:
[ ][ ][ ][1][2][3][ ]
如果此时从缓冲区中移除两个元素,那么缓冲区里最旧的值会被移除。 在这个例子中,被移除的两个元素是 1 和 2,缓冲区里只剩下一个 3:
[ ][ ][ ][ ][ ][3][ ]
如果缓冲区里有 7 个元素,那么它就完全满了:
[5][6][7][8][9][3][4]
当缓冲区已满时,会引发一个错误,提醒客户端:在有位置空出来之前,后续的写入都会被阻断。
当缓冲区已满时,客户端可以选择用强制写入来覆盖最旧的数据。 在这个例子中,又加入了两个元素 A 和 B,它们覆盖掉了 3 和 4:
[5][6][7][8][9][A][B]
3 和 4 已经被 A 和 B 取代,因此 5 现在成了缓冲区里最旧的数据。 最后,如果移除两个元素,那么返回的将会是 5 和 6,缓冲区变成:
[ ][ ][7][8][9][A][B]
因为有空位可用,如果客户端再次使用覆盖写入来存放 C 和 D,那么会用到之前存放 5 和 6 的位置,而不是 7 和 8 所在的位置。 7 仍然是最旧的元素,缓冲区又再次满了。
[C][D][7][8][9][A][B]
有时,你需要在代码中同时自定义和raise异常。这样做时,一定要附上一句有意义的错误信息,说明错误的来源是什么。这会让你的代码更易读,对调试也有很大帮助。
自定义异常可以通过创建新的异常类来实现(详见classes),这些异常类通常是Exception的子类。
如果你知道错误的来源会是某种异常类型的派生类,可以选择继承 Exception 类下的某个built in error types。抛出错误时,仍然要附上一条有意义的信息。
这个练习要求你创建两个_自定义异常_。一个用于在循环缓冲区满时抛出(也就是“thrown”),另一个用于缓冲区空时。只有当你自定义了合适的异常、raise这些异常,并附上合适的错误信息时,测试才会通过。
要自定义built-in exception,请创建一个继承该异常的class。抛出带信息的自定义异常时,把这条信息作为参数传给exception类型:
# subclassing the built-in BufferError to create BufferFullException
class BufferFullException(BufferError):
"""Exception raised when CircularBuffer is full.
message: explanation of the error.
"""
def __init__(self, message):
self.message = message
# raising a BufferFullException
raise BufferFullException("Circular buffer is full")