您将如何用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.

赞:(猎杀问题留给了用户)

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屋！