http://tutorials.jenkov.com/java-performance/ring-buffer.html
The ring buffer has a read position and a write position which marks the next position to read from and write to the ring buffer. When the write position reaches the end of the array, the write position is set back to 0. The same is true for the read position.
Batch Modes
第二个问题就是代码， 让实现一个ringbuffer。心里窃喜。但由于些许紧张写的过程并不是非常流畅，也是吭哧吭哧写完了。
- 主要就是实现一个写入函数，一个读取函数（读取最旧的一个值）。
- 写完之后让写一下测试，口述一下运行过程。
- 然后说一下每个函数的复杂度，（这个复杂度实现出来肯定就是O（1）了）
The ring buffer has a read position and a write position which marks the next position to read from and write to the ring buffer. When the write position reaches the end of the array, the write position is set back to 0. The same is true for the read position.
Ring buffers are especially useful when you need a hard upper bound for how much data can be in the ring buffer (in the queue).
If you don't want an upper bound on your queue structure, perhaps you should be using a linked list, or a ring buffer that can resize itself (allocate a new, bigger array when it is full, and move all elements to that array).
Ring Buffer Using Fill Count
One way to keep track of write position, read position and the number of elements in the ring buffer is to use a write position and a fill count. The write position marks the next position in the ring buffer to write an element to. The fill count tells how many elements are currently stored in the buffer.
When writing elements to the ring buffer it just has to check the fill count to see if it is full or not. If it is not full the element can be inserted at the write position and the write position advanced to the next free slot.
Similarly, when reading elements from the ring buffer it just has to check the fill count to see if the ring buffer is empty. The read position is calculated by subtracting the fill count from the write position. If the result of that calculation is negative, the write position has wrapped around, and you need to add the size of the buffer (array) to the read position to get the correct read position.
Below is a ring buffer implementation that uses a fill count. Notice that it does not track the read position explicitly, but calculates the read position based on the write position and the fill count. Notice also, that the fill count field is called
available (not fillCount).
Ring Buffer Using Flip Marker
Another option to keep track of read position, write position and how many elements are in the buffer, is to simply keep a read position in addition to the write position.
How many elements are in the buffer is calculated based on the write and read position. How the calculation looks depends on whether the write position has flipped (wrapped around) or not.
If the write position has not wrapped around you can simply subtract the read position from the write position to know how many elements are in the buffer. If the write position has wrapped around (flipped) then the available space is equal to the capacity minus the read position plus the write position.
To keep track of whether the write position has flipped or not a special "flip marker" is used. That is where the name of the implementation comes from. Actually, in most cases you could just check if the write position is larger or smaller than the read position to detect if the write position has wrapped around. But, that doesn't work when write position and read position are equal (the ring buffer is either completely full or completely empty).
Batch Modes
public class RingBufferFillCount {
public Object[] elements = null;
public int capacity = 0;
public int writePos = 0;
public int available = 0;
public QueueFillCount(int capacity) {
this.capacity = capacity;
this.elements = new Object[capacity];
}
public void reset() {
this.writePos = 0;
this.available = 0;
}
public int remainingCapacity() {
return this.capacity - this.available;
}
public boolean put(Object element){
if(available < capacity){
if(writePos >= capacity){
writePos = 0;
}
elements[writePos] = element;
writePos++;
available++;
return true;
}
return false;
}
public int put(Object[] newElements){
return put(newElements, newElements.length);
}
public int put(Object[] newElements, int length){
int readPos = 0;
if(this.writePos > this.available){
//space above writePos is all empty
if(length <= this.capacity - this.writePos){
//space above writePos is sufficient to insert batch
for(; readPos < length; readPos++){
this.elements[this.writePos++] = newElements[readPos];
}
this.available += readPos;
return length;
} else {
//both space above writePos and below writePos is necessary to use
//to insert batch.
int lastEmptyPos = writePos - available;
for(; this.writePos < this.capacity; this.writePos++){
this.elements[this.writePos] = newElements[readPos++];
}
//fill into bottom of array too.
this.writePos = 0;
int endPos = Math.min(length - readPos, capacity - available - readPos);
for(;this.writePos < endPos; this.writePos++){
this.elements[this.writePos] = newElements[readPos++];
}
this.available += readPos;
return readPos;
}
} else {
int endPos = this.capacity - this.available + this.writePos;
for(; this.writePos < endPos; this.writePos++){
this.elements[this.writePos] = newElements[readPos++];
}
this.available += readPos;
return readPos;
}
}
public Object take() {
if(available == 0){
return null;
}
int nextSlot = writePos - available;
if(nextSlot < 0){
nextSlot += capacity;
}
Object nextObj = elements[nextSlot];
available--;
return nextObj;
}
public int take(Object[] into){
return take(into, into.length);
}
public int take(Object[] into, int length){
int intoPos = 0;
if(available <= writePos){
int nextPos= writePos - available;
int endPos = nextPos + Math.min(available, length);
for(;nextPos < endPos; nextPos++){
into[intoPos++] = this.elements[nextPos];
}
this.available -= intoPos;
return intoPos;
} else {
int nextPos = writePos - available + capacity;
int leftInTop = capacity - nextPos;
if(length <= leftInTop){
//copy directly
for(; intoPos < length; intoPos++){
into[intoPos] = this.elements[nextPos++];
}
this.available -= length;
return length;
} else {
//copy top
for(; nextPos < capacity; nextPos++){
into[intoPos++] = this.elements[nextPos];
}
//copy bottom - from 0 to writePos
nextPos = 0;
int leftToCopy = length - intoPos;
int endPos = Math.min(writePos, leftToCopy);
for(;nextPos < endPos; nextPos++){
into[intoPos++] = this.elements[nextPos];
}
this.available -= intoPos;
return intoPos;
}
}
}
}
public class RingBufferFlip {
public Object[] elements = null;
public int capacity = 0;
public int writePos = 0;
public int readPos = 0;
public boolean flipped = false;
public QueueFlip(int capacity) {
this.capacity = capacity;
this.elements = new Object[capacity];
}
public void reset() {
this.writePos = 0;
this.readPos = 0;
this.flipped = false;
}
public int available() {
if(!flipped){
return writePos - readPos;
}
return capacity - readPos + writePos;
}
public int remainingCapacity() {
if(!flipped){
return capacity - writePos;
}
return readPos - writePos;
}
public boolean put(Object element){
if(!flipped){
if(writePos == capacity){
writePos = 0;
flipped = true;
if(writePos < readPos){
elements[writePos++] = element;
return true;
} else {
return false;
}
} else {
elements[writePos++] = element;
return true;
}
} else {
if(writePos < readPos ){
elements[writePos++] = element;
return true;
} else {
return false;
}
}
}
public int put(Object[] newElements, int length){
int newElementsReadPos = 0;
if(!flipped){
//readPos lower than writePos - free sections are:
//1) from writePos to capacity
//2) from 0 to readPos
if(length <= capacity - writePos){
//new elements fit into top of elements array - copy directly
for(; newElementsReadPos < length; newElementsReadPos++){
this.elements[this.writePos++] = newElements[newElementsReadPos];
}
return newElementsReadPos;
} else {
//new elements must be divided between top and bottom of elements array
//writing to top
for(;this.writePos < capacity; this.writePos++){
this.elements[this.writePos] = newElements[newElementsReadPos++];
}
//writing to bottom
this.writePos = 0;
this.flipped = true;
int endPos = Math.min(this.readPos, length - newElementsReadPos);
for(; this.writePos < endPos; this.writePos++){
this.elements[writePos] = newElements[newElementsReadPos++];
}
return newElementsReadPos;
}
} else {
//readPos higher than writePos - free sections are:
//1) from writePos to readPos
int endPos = Math.min(this.readPos, this.writePos + length);
for(; this.writePos < endPos; this.writePos++){
this.elements[this.writePos] = newElements[newElementsReadPos++];
}
return newElementsReadPos;
}
}
public Object take() {
if(!flipped){
if(readPos < writePos){
return elements[readPos++];
} else {
return null;
}
} else {
if(readPos == capacity){
readPos = 0;
flipped = false;
if(readPos < writePos){
return elements[readPos++];
} else {
return null;
}
} else {
return elements[readPos++];
}
}
}
public int take(Object[] into, int length){
int intoWritePos = 0;
if(!flipped){
//writePos higher than readPos - available section is writePos - readPos
int endPos = Math.min(this.writePos, this.readPos + length);
for(; this.readPos < endPos; this.readPos++){
into[intoWritePos++] = this.elements[this.readPos];
}
return intoWritePos;
} else {
//readPos higher than writePos - available sections are
//top + bottom of elements array
if(length <= capacity - readPos){
//length is lower than the elements available at the top
//of the elements array - copy directly
for(; intoWritePos < length; intoWritePos++){
into[intoWritePos] = this.elements[this.readPos++];
}
return intoWritePos;
} else {
//length is higher than elements available at the top of the elements array
//split copy into a copy from both top and bottom of elements array.
//copy from top
for(; this.readPos < capacity; this.readPos++){
into[intoWritePos++] = this.elements[this.readPos];
}
//copy from bottom
this.readPos = 0;
this.flipped = false;
int endPos = Math.min(this.writePos, length - intoWritePos);
for(; this.readPos < endPos; this.readPos++){
into[intoWritePos++] = this.elements[this.readPos];
}
return intoWritePos;
}
}
}
}
http://www.1point3acres.com/bbs/thread-171867-1-1.html第二个问题就是代码， 让实现一个ringbuffer。心里窃喜。但由于些许紧张写的过程并不是非常流畅，也是吭哧吭哧写完了。
- 主要就是实现一个写入函数，一个读取函数（读取最旧的一个值）。
- 写完之后让写一下测试，口述一下运行过程。
- 然后说一下每个函数的复杂度，（这个复杂度实现出来肯定就是O（1）了）
- public class RingBuffer {
- public Object[] elements = null;
- private int capacity = 0;
- private int writePos = 0;. 涓€浜�-涓夊垎-鍦帮紝鐙鍙戝竷
- private int available = 0;
- public RingBuffer(int capacity) {
- this.capacity = capacity;. 鐗涗汉浜戦泦,涓€浜╀笁鍒嗗湴
- this.elements = new Object[capacity];
- }
- public void reset() {
- this.writePos = 0;
- this.available = 0;
- }. from: 1point3acres.com/bbs
- public int capacity() {
- return this.capacity;
- }
- public int available() {
- return this.available;
- }
- public int remainingCapacity() {
- return this.capacity - this.available;
- }
- public boolean put(Object element) {
- . Waral 鍗氬鏈夋洿澶氭枃绔�,
- if (available < capacity) {
- if (writePos >= capacity) {
- writePos = 0;
- }
- elements[writePos] = element;
- writePos++;. 1point 3acres 璁哄潧
- available++;
- return true;
- }
- return false;
- }
- . 1point3acres.com/bbs
- public Object take() {
- if (available == 0) {
- return null;
- }-google 1point3acres
- int nextSlot = writePos - available;
- if (nextSlot < 0) {. 涓€浜�-涓夊垎-鍦帮紝鐙鍙戝竷
- nextSlot += capacity;
- }. 鐣欏鐢宠璁哄潧-涓€浜╀笁鍒嗗湴
- Object nextObj = elements[nextSlot];
- available--;
- return nextObj;
- }. 鐣欏鐢宠璁哄潧-涓€浜╀笁鍒嗗湴
- }
