是什么？
RingBuffer （环形缓冲区），是一种用于表示一个固定尺寸、头尾相连的缓冲区的数据结构，适合缓存数据流（用来实现轮转功能的日志也很合适）。
它亦是一个队列，先进先出(FIFO)。这意味着，入队永远是在环的尾部(tail)，出队永远是在环的头部(head)。这个环的容量是一开始就确定的，那么不停变换的，是头尾两个指针：入队驱动tail，出队驱动head，在环上单向轮转。
性能优势
我们可以将RingBuffer实现为一个不停覆盖尾部的版本， 以提供一种高性能的有限无锁队列：
- 它使用数组，比链表要快，且基于一个可预测的访问模式（数组内元素的内存地址 具有连续性），意味着它是CPU缓存友好的——在硬件级别，数组中的元素是会被预加载的;
- 在程序生命周期内，这个数组会一直存在，不需要经常做垃圾回收（没有抖动就没有伤害）。
一个Scala实现
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
class RingBuffer[T: Manifest](capacity: Int) { private var _head = 0 private var _tail = 0 private var _size = 0 private val queue = new Array[T](capacity) def size: Int = this._size def isEmpty: Boolean = this._size == 0 def isFull: Boolean = this._size == capacity def peek: T = this.queue(this._head) def enqueue(elem: T): Int = { this.queue(this._tail) = elem if (!this.isFull) this._size += 1 else this._head = (this._head + 1) % this.capacity this._tail = (this._head + this._size) % this.capacity this.size } def dequeue: T = { if (this.isEmpty) throw new Exception("RingBuffer is empty") val elem = this.peek this._size -= 1 this._head = (this._head + 1) % this.capacity elem } } |
一个Scala测试
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
import org.scalatest._ class RingBufferSpec extends FunSpec with Matchers { describe("A RingBuffer") { val ringBuffer = new RingBuffer[Int](3) it("should have a fixed-size") { var size = ringBuffer.enqueue(1) size should be (1) size = ringBuffer.enqueue(2) size should be (2) size = ringBuffer.enqueue(3) size should be (3) size = ringBuffer.enqueue(4) size should be (3) } it("should be a circular queue") { var elem = ringBuffer.dequeue elem should be (2) elem = ringBuffer.dequeue elem should be (3) elem = ringBuffer.dequeue elem should be (4) } } } |
打赏作者
您的支持将激励我继续创作！
RSS Feed
有木有多线程问题?
没测过，个人觉得问题不大
不行也可以改成无副作用的
这个是什么语言啊？
Scala