Circular buffer

Circular buffer

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

前言:

circular buffercyclic buffer or ring buffer is a data structure that uses a single, fixed-size buffer as if it were connected end-to-end. This structure lends itself easily to buffering data streams.

Uses

The useful property of a circular buffer is that it does not need to have its elements shuffled around [又一次排列]when one is consumed. (If a non-circular buffer were used then it would be necessary to shift all elements when one is consumed.) In other words, the circular buffer is well-suited[很合适] as a FIFO [先进先出]buffer while a standard, non-circular buffer is well suited as a LIFO [后进后出]buffer.

Circular buffering makes a good implementation strategy for a queue that has fixed maximum size. Should a maximum size be adopted [被採用]for a queue, then a circular buffer is a completely ideal implementation; all queue operations are constant time. However, expanding a circular buffer requires shifting memory, which is comparatively[相对来说] costly. For arbitrarily expanding queues[可任意扩展的], a linked list approach[链表] may be preferred instead.

[本文作者franklin注解]环形buffer 应用于固定的块场合,一旦固定,这块内存就是专用,所以,不具备扩展性.

In some situations, overwriting [可覆盖性]circular buffer can be used, e.g. in multimedia. If the buffer is used as the bounded [有界性,有限制] buffer in the producer-consumer problem then it is probably desired for the producer (e.g., an audio generator) to overwrite old data if the consumer (e.g., the sound card) is unable to momentarily keep up. Also, the LZ77 family of lossless data compression algorithms operates on the assumption that strings seen more recently in a data stream are more likely to occur soon in the stream. Implementations store the most recent data in a circular buffer.

How it works

A circular buffer first starts empty and of some predefined length. For example, this is a 7-element buffer:

Circular buffer - empty.svg

Assume that a 1 is written into the middle of the buffer (exact starting location does not matter in a circular buffer):

Circular buffer - XX1XXXX.svg

Then assume that two more elements are added — 2 & 3 — which get appended after the 1:

Circular buffer - XX123XX.svg

If two elements are then removed from the buffer, the oldest values inside the buffer are removed. The two elements removed, in this case, are 1 & 2, leaving the buffer with just a 3:

Circular buffer - XXXX3XX.svg

If the buffer has 7 elements then it is completely full:

Circular buffer - 6789345.svg

A consequence of the circular buffer is that when it is full and a subsequent write is performed, then it starts overwriting the oldest data. In this case, two more elements — A & B — are added and they overwrite the 3 & 4:

[本文作者franklin注解][当环形buffer满的时候,兴许写入数据将覆盖前面数据]

Circular buffer - 6789AB5.svg

Alternatively[或者], the routines that manage the buffer could prevent overwriting the data and return an error or raise[根本就是设计成不能写入] an exception. Whether or not data is overwritten is up to the semantics of the buffer routines or the application using the circular buffer.

Finally, if two elements are now removed then what would be returned is not 3 & 4 but 5 & 6 because A & B overwrote the 3 & the 4 yielding the buffer with:

Circular buffer - X789ABX.svg


Circular buffer mechanics

What is not shown in the example above is the mechanics of how the circular buffer is managed.

Start/end pointers (head/tail)[edit]

Generally, a circular buffer requires four pointers:

  • one to the actual buffer in memory
  • one to the buffer end in memory (or alternately[取代]: the size of the buffer)
  • one to point to the start of valid data (or alternately: amount of data written to the buffer)
  • one to point to the end of valid data (or alternately: amount of data read from the buffer)

Alternatively[或者], a fixed-length buffer with two integers to keep track of indices can be used in languages that do not have pointers.

[没有指针也能够的]

Taking a couple of examples from above. (While there are numerous[庞大的] ways to label the pointers and exact semantics[精确到语意]can vary, this is one way to do it.)

This image shows a partially[部分] full buffer:

Circular buffer - XX123XX with pointers.svg

This image shows a full buffer with two elements having been overwritten:

Circular buffer - 6789AB5 with pointers.svg

What to note about the second one is that after each element is overwritten then the start pointer is incremented as well.

Difficulties

Full / Empty Buffer Distinction

A small disadvantage of relying on pointers or relative indices of the start and end of data is, that in the case the buffer is entirely full, both pointers point to the same element:

Circular buffer - 6789AB5 full.svg

This is exactly the same situation as when the buffer is empty:

Circular buffer - 6789AB5 empty.svg

[最常见的问题是,buffer的满和空的判别]

To solve this confusion there are a number of solutions:

Always Keep One Slot Open [最简单有效的解决的方法就是保持最后一个单元不写]

This design always keeps one slot unallocated. A full buffer has at most (\text{size}-1) slots. If both pointers refer to the same slot, the buffer is empty. If the end (write) pointer refers to the slot preceding the one referred to by the start (read) pointer, the buffer is full.

The advantage is:

  • The solution is simple and robust.

The disadvantages are:

  • One slot is lost, so it is a bad compromise when the buffer size is small or the slot is big or is implemented in hardware.
  • The full test requires a modulo operation

ref:

http://en.wikipedia.org/wiki/Circular_buffer

http://lmax-exchange.github.io/disruptor/

http://www.cnblogs.com/shanyou/archive/2013/02/04/2891300.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/116759.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • Spring 核心控制器DispatcherServlet(三)

    Spring 核心控制器DispatcherServlet(三)

  • 哈夫曼实现文件压缩解压缩(c语言)

    哈夫曼实现文件压缩解压缩(c语言)写一个对文件进行压缩和解压缩的程序,功能如下:①可以对纯英文文档实现压缩和解压;②较好的界面程序运行的说明。介绍哈夫曼:效率最高的判别树即为哈夫曼树在计算机数据处理中,霍夫曼编码使用变长编码表对源符号(如文件中的一个字母)进行编码,其中变长编码表是通过一种评估来源符号出现机率的方法得到的,出现机率高的字母使用较短的编码,反之出现机率低的则使用较长的…

  • BigDecimal 与 int,long,double之间的互转[通俗易懂]

    BigDecimal 与 int,long,double之间的互转[通俗易懂]BigDecimal与int,long,double之间的互转转换关系如下:int转换成BigDecimal/***int转Bigdecimal*/@Testpublicvoiddemo04(){inta=101;BigDecimalbig=newBigDecimal(a);System.out.prin…

  • Java IO流自动关闭

    Java IO流自动关闭Filef=newFile();Filedes=newFile();try(FileInputStreaminput=newFileInputStream(f);FileOutputStreamout=newFileOutputStream(des);){}catch(FileNotFoundExceptione1){ }catch(IO…

  • Unix命令「建议收藏」

    Unix命令「建议收藏」1.在文件中查找关键字1)命令格式:find 路径 -name"文件名"|xargsgrep关键字比如:查找当前目录下的所有包含12345的log

  • bios刷写工具_蓝天P750/P751编程器刷BIOS「建议收藏」

    bios刷写工具_蓝天P750/P751编程器刷BIOS「建议收藏」神舟ZX8-SP7是蓝天P751DM2模具,今天在WIN下刷BIOS成功刷黑,开始使用编程器刷BIOS,笔记本BIOS芯片由于是焊在主板上必须用夹子或者脱焊后用烧录座刷写,所以需要买编程器夹子。工具:优硕EZP-XPROV2、优硕SOP8编程器夹子。目标:神舟ZX8-SP7(P751DM2模具)准备工作:去蓝天镜像站下载对应的模具的BIOS蓝天镜像站:https://repo.palkeo.co…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号