您将如何用 Java 或 C# 编写高效的循环缓冲区? [英] How would you code an efficient Circular Buffer in Java or C#?

问题描述

我想要一个简单的类来实现一个固定大小的循环缓冲区.它应该是高效的、易于理解的、通用的类型.

I want a simple class that implements a fixed-size circular buffer. It should be efficient, easy on the eyes, generically typed.

现在不需要支持MT.以后可以随时加锁，反正不会高并发.

For now it need not be MT-capable. I can always add a lock later, it won't be high-concurrency in any case.

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

Methods should be: .Add() and I guess .List(), where I retrieve all the entries. On second thought, Retrieval I think should be done via an indexer. At any moment I will want to be able to retrieve any element in the buffer by index. But keep in mind that from one moment to the next Element[n] may be different, as the circular buffer fills up and rolls over. This isn't a stack, it's a circular buffer.

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

Regarding "overflow": I would expect internally there would be an array holding the items, and over time the head and tail of the buffer will rotate around that fixed array. But that should be invisible from the user. There should be no externally-detectable "overflow" event or behavior.

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

This is not a school assignment - it is most commonly going to be used for a MRU cache or a fixed-size transaction or event log.

推荐答案

我会使用一个 T 数组、一个头尾指针，以及 add 和 get 方法.

I would use an array of T, a head and tail pointer, and add and get methods.

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

Like: (Bug hunting is left to the user)

// 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();
    }
  }
}

这篇关于您将如何用 Java 或 C# 编写高效的循环缓冲区?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！