c# - 您将如何用 Java 或 C# 编写高效的循环缓冲区？

Question

我想要一个实现固定大小的简单类 circular buffer .它应该是高效的、易于理解的、通用类型的。

目前不需要 MT-capable .以后可以随时加锁，反正不会是高并发的。

方法应该是:.Add() 我猜是 .List()，我在其中检索所有条目。转念一想，检索我认为应该通过索引器来完成。在任何时候我都希望能够通过 index 检索缓冲区中的任何元素。但请记住，从一个时刻到下一个 Element[n] 可能会有所不同，因为 循环缓冲区 会填满并翻转。这不是一个堆栈，它是一个循环缓冲区。

关于“溢出”:我希望内部会有一个数组来保存项目，随着时间的推移，head 和 tail缓冲区将围绕该固定数组旋转。但这对用户来说应该是不可见的。不应有外部可检测的“溢出”事件或行为。

这不是学校作业 - 它最常用于 MRU cache或固定大小的事务或事件日志。

Answer 1

我会使用 T 数组、头指针和尾指针，以及添加和获取方法。

喜欢:(Bug 搜索留给用户)

// Hijack these for simplicity
import java.nio.BufferOverflowException;
import java.nio.BufferUnderflowException;

public class CircularBuffer<T> {

  private T[] buffer;

  private int tail;

  private int head;

  @SuppressWarnings("unchecked")
  public CircularBuffer(int n) {
    buffer = (T[]) new Object[n];
    tail = 0;
    head = 0;
  }

  public void add(T toAdd) {
    if (head != (tail - 1)) {
        buffer[head++] = toAdd;
    } else {
        throw new BufferOverflowException();
    }
    head = head % buffer.length;
  }

  public T get() {
    T t = null;
    int adjTail = tail > head ? tail - buffer.length : tail;
    if (adjTail < head) {
        t = (T) buffer[tail++];
        tail = tail % buffer.length;
    } else {
        throw new BufferUnderflowException();
    }
    return t;
  }

  public String toString() {
    return "CircularBuffer(size=" + buffer.length + ", head=" + head + ", tail=" + tail + ")";
  }

  public static void main(String[] args) {
    CircularBuffer<String> b = new CircularBuffer<String>(3);
    for (int i = 0; i < 10; i++) {
        System.out.println("Start: " + b);
        b.add("One");
        System.out.println("One: " + b);
        b.add("Two");
        System.out.println("Two: " + b);
        System.out.println("Got '" + b.get() + "', now " + b);

        b.add("Three");
        System.out.println("Three: " + b);
        // Test Overflow
        // b.add("Four");
        // System.out.println("Four: " + b);

        System.out.println("Got '" + b.get() + "', now " + b);
        System.out.println("Got '" + b.get() + "', now " + b);
        // Test Underflow
        // System.out.println("Got '" + b.get() + "', now " + b);

        // Back to start, let's shift on one
        b.add("Foo");
        b.get();
    }
  }
}