当前位置:  开发笔记 > 编程语言 > 正文

您将如何使用Java或C#编写高效的循环缓冲区?

如何解决《您将如何使用Java或C#编写高效的循环缓冲区?》经验,为你挑选了3个好方法。

我想要一个实现固定大小循环缓冲区的简单类.它应该是高效的,容易在眼睛上,一般打字.

编辑:目前它不需要具备MT功能.我总是可以在以后添加一个锁,在任何情况下它都不会是高并发性的.

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

这不是一个堆栈,它是一个循环缓冲区.关于"溢出":我希望内部会有一个包含项目的数组,随着时间的推移,缓冲区的头部和尾部将围绕该固定数组旋转.但这应该是用户不可见的.应该没有外部可检测的"溢出"事件或行为.

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



1> JeeBee..:

我会使用T数组,头部和尾部指针,以及添加和获取方法.

喜欢:(漏洞留给用户)

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

public class CircularBuffer {

  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 b = new CircularBuffer(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();
    }
  }
}


我确信那个花了超过5分钟在网络论坛上写一个答案的人(我说"将bug留给用户")会有更好的实施.
除非我严重误解规范,否则此代码存在重大缺陷.如果不尝试检索元素,则可以将无限数量的元素插入队列而不会获得BufferOverflowException.在http://www.cs.utsa.edu/~wagner/CS2213/queue/queue.html上有一个更好的实现.
发现一个错误:从内部数组中删除元素后,get()方法未将内部数组的元素设置为“ null”,因此会出现轻微的内存泄漏。

2> Scott S. McC..:

这是我会怎样(或没有)用Java编写高效的循环缓冲区.它由一个简单的数组支持.对于我的特定用例,我需要高并发吞吐量,所以我使用CAS来分配索引.然后,我创建了可靠副本的机制,包括整个缓冲区的CAS副本.我在短篇文章中更详细地概述了一个案例.

import java.util.concurrent.atomic.AtomicLong;
import java.lang.reflect.Array;

/**
 * A circular array buffer with a copy-and-swap cursor.
 *
 * 

This class provides an list of T objects who's size is unstable. * It's intended for capturing data where the frequency of sampling greatly * outweighs the frequency of inspection (for instance, monitoring).

* *

This object keeps in memory a fixed size buffer which is used for * capturing objects. It copies the objects to a snapshot array which may be * worked with. The size of the snapshot array will vary based on the * stability of the array during the copy operation.

* *

Adding buffer to the buffer is O(1), and lockless. Taking a * stable copy of the sample is O(n).

*/ public class ConcurrentCircularBuffer { private final AtomicLong cursor = new AtomicLong(); private final T[] buffer; private final Class type; /** * Create a new concurrent circular buffer. * * @param type The type of the array. This is captured for the same reason * it's required by {@link java.util.List.toArray()}. * * @param bufferSize The size of the buffer. * * @throws IllegalArgumentException if the bufferSize is a non-positive * value. */ public ConcurrentCircularBuffer (final Class type, final int bufferSize) { if (bufferSize < 1) { throw new IllegalArgumentException( "Buffer size must be a positive value" ); } this.type = type; this.buffer = (T[]) new Object [ bufferSize ]; } /** * Add a new object to this buffer. * *

Add a new object to the cursor-point of the buffer.

* * @param sample The object to add. */ public void add (T sample) { buffer[(int) (cursor.getAndIncrement() % buffer.length)] = sample; } /** * Return a stable snapshot of the buffer. * *

Capture a stable snapshot of the buffer as an array. The snapshot * may not be the same length as the buffer, any objects which were * unstable during the copy will be factored out.

* * @return An array snapshot of the buffer. */ public T[] snapshot () { T[] snapshots = (T[]) new Object [ buffer.length ]; /* Determine the size of the snapshot by the number of affected * records. Trim the size of the snapshot by the number of records * which are considered to be unstable during the copy (the amount the * cursor may have moved while the copy took place). * * If the cursor eliminated the sample (if the sample size is so small * compared to the rate of mutation that it did a full-wrap during the * copy) then just treat the buffer as though the cursor is * buffer.length - 1 and it was not changed during copy (this is * unlikley, but it should typically provide fairly stable results). */ long before = cursor.get(); /* If the cursor hasn't yet moved, skip the copying and simply return a * zero-length array. */ if (before == 0) { return (T[]) Array.newInstance(type, 0); } System.arraycopy(buffer, 0, snapshots, 0, buffer.length); long after = cursor.get(); int size = buffer.length - (int) (after - before); long snapshotCursor = before - 1; /* Highly unlikely, but the entire buffer was replaced while we * waited...so just return a zero length array, since we can't get a * stable snapshot... */ if (size <= 0) { return (T[]) Array.newInstance(type, 0); } long start = snapshotCursor - (size - 1); long end = snapshotCursor; if (snapshotCursor < snapshots.length) { size = (int) snapshotCursor + 1; start = 0; } /* Copy the sample snapshot to a new array the size of our stable * snapshot area. */ T[] result = (T[]) Array.newInstance(type, size); int startOfCopy = (int) (start % snapshots.length); int endOfCopy = (int) (end % snapshots.length); /* If the buffer space wraps the physical end of the array, use two * copies to construct the new array. */ if (startOfCopy > endOfCopy) { System.arraycopy(snapshots, startOfCopy, result, 0, snapshots.length - startOfCopy); System.arraycopy(snapshots, 0, result, (snapshots.length - startOfCopy), endOfCopy + 1); } else { /* Otherwise it's a single continuous segment, copy the whole thing * into the result. */ System.arraycopy(snapshots, startOfCopy, result, 0, endOfCopy - startOfCopy + 1); } return (T[]) result; } /** * Get a stable snapshot of the complete buffer. * *

This operation fetches a snapshot of the buffer using the algorithm * defined in {@link snapshot()}. If there was concurrent modification of * the buffer during the copy, however, it will retry until a full stable * snapshot of the buffer was acquired.

* *

Note, for very busy buffers on large symmetric multiprocessing * machines and supercomputers running data processing intensive * applications, this operation has the potential of being fairly * expensive. In practice on commodity hardware, dualcore processors and * non-processing intensive systems (such as web services) it very rarely * retries.

* * @return A full copy of the internal buffer. */ public T[] completeSnapshot () { T[] snapshot = snapshot(); /* Try again until we get a snapshot that's the same size as the * buffer... This is very often a single iteration, but it depends on * how busy the system is. */ while (snapshot.length != buffer.length) { snapshot = snapshot(); } return snapshot; } /** * The size of this buffer. */ public int size () { return buffer.length; } }


@nos —是的,很不错,尽管任何程序运行足够长的时间以使很多东西通过此缓冲区都将是令人印象深刻的,但我已经着手将其转换为用于光标跟踪的时间。对于所有实际目的来说,这应该是足够的值...

3> Museful..:

这是我在生产代码中使用的Java的现成的CircularArrayList实现。通过以Java建议的方式重写AbstractList,它支持Java Collections Framework中标准List实现所期望的所有功能(通用元素类型,subList,迭代等)。

以下调用在O(1)中完成:

add(item)-在列表末尾添加

remove(0)-从列表的开头删除

get(i)-检索列表中的随机元素

推荐阅读
手机用户2502852037
这个屌丝很懒,什么也没留下!
DevBox开发工具箱 | 专业的在线开发工具网站    京公网安备 11010802040832号  |  京ICP备19059560号-6
Copyright © 1998 - 2020 DevBox.CN. All Rights Reserved devBox.cn 开发工具箱 版权所有