轨道
/
Julia
Julia
/
练习
/
环形缓冲区
环形缓冲区

环形缓冲区

困难

说明

环形缓冲区(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]

任务

定义一个参数化复合类型CircularBuffer{T},用来保存类型为T的元素,并写一个构造函数

CircularBuffer{T}(capacity::Integer) where {T} -> CircularBuffer{T}

用来创建一个最多可存储capacity个元素的实例。

扩展Base中的以下函数,让它们能作用于CircularBuffer:

  • Base.push!(cb::CircularBuffer, item; overwrite::Bool=false):把元素item插入cb的末尾,然后返回cb。如果cb已经满了,那么当overwrite为false(默认值)时抛出BoundsError;否则,如果overwrite为true,就先移除第一个元素,为item腾出空间。
  • Base.popfirst!(cb::CircularBuffer):移除并返回cb的第一个元素。
  • Base.empty!(cb::CircularBuffer):移除cb中的所有元素,然后返回空的cb。

加分任务

这个练习规模相当大,也可能很复杂,这让指导工作更有挑战性,也更费时间。为了给导师减轻负担,请等导师审阅过你练习第一部分的解答之后,再提交加分题的代码。

扩展你的CircularBuffer,让它能通过 DataStructures.jl包中CircularBuffer的测试。这些测试已经包含在本 Exercism 练习所提供的测试里,只不过被禁用了;要启用它们,请在文件或 notebook 的顶层加上一行enable_bonus_tests = true。

要通过这些测试,你需要把CircularBuffer声明为AbstractVector的子类型,并定义两个函数:

  • capacity(cb::CircularBuffer):返回cb的容量。
  • isfull(cb::CircularBuffer):如果cb已满,就返回true。

然后你还必须确保Base中的以下函数能与CircularBuffer正确配合:append!、empty!、pop!、pushfirst、setindex!、collect、eltype、first、getindex、isempty、iterate、last、length和size。

提示:你不需要,也不应该去扩展所有这些函数!只要把CircularBuffer定义为AbstractVector的子类型,原本为AbstractVector定义的泛型函数现在就会接受CircularBuffer作为输入。参见 Julia 手册中关于接口的一节:

Julia 的许多强大之处和可扩展性,都来自一系列非正式的接口。只要为自定义类型扩展几个特定的方法,该类型的对象就不仅能获得这些功能,还能用在其他以这些行为为基础、通用地构建起来的方法里。

你需要翻阅 Julia 的Base模块源代码来查看函数定义,弄清该扩展哪些函数。要定位某次函数调用对应的代码,你可以用@which宏来找出这次调用具体分发到了哪个方法。它还会显示该方法定义所在的文件和行号(在 Jupyter Notebook 里通过 IJulia,它甚至会给出指向 GitHub 上相关代码的链接)。

如果你在 REPL 里工作,也许更想用@edit宏,在你默认的文本编辑器里打开相关的文件和行。


来源

Wikipedia链接会在新窗口或新标签页中打开
通过 GitHub 编辑 链接将在新窗口或新标签页中打开
Julia Exercism

准备好开始 环形缓冲区 了吗?

注册 Exercism,借助 35 个概念128 个练习 和真人导师指导,学习并掌握 Julia,全部免费。

深入探索 环形缓冲区!

在这个视频里,我们来看看环形缓冲区:它是什么、用在哪些地方,以及各种不同的实现方式,包括队列、静态数组和动态数组、不可变数据结构,还有一个有趣的基于代理的实现。