Java - 在巨人列表中追加和删除的最佳策略？

Question

使用Java.

我为一些计算等记录小物件,我只需要最后的一千个.所以我想先发布垃圾收集器.但是因为从ArrayLists中删除是昂贵的...

以下是重要的(不能改变)

• 没有DB
• 对象是相同的类型
• 每秒最多50,000个对象
• 表现很重要
• 快速迭代整个列表很重要
• 随机访问也很重要

这可以改变:

• 现在正在使用 ArrayList<MyObject>
• 限制:100,000个对象(停止录制,但必须继续)

我的猜测:

• 链表
• RingBuffer
• ???

我能做些什么来快速迭代并同时快速释放旧对象？

Answer 1

一个办法

... 如果需要恒定数量的最后元素,只需使用数组作为环形缓冲区的基础.

• 单一分配

• 没有得到/放/等.内联时的方法开销

• 简单

一个示例(可能无法编译,即时编写)实现:

class LastElementsStore<T> {
  Object[] arr;
  int size;
  int nextPutIndex;

  LastElementsStore(int size ) {
    arr = new Object[size];
    this.size = size;
  }

  void put(T elt) {
    arr[nextPutIndex] = elt;
    nextPutIndex++;
    if (nextPutIndex == size) {
      nextPutIndex = 0;
    }
  }

  // getters of your choice

}

如果没有足够的元素,则返回空值.

如果您需要它们,请从nextPutIndex开始,一直读到最后,然后转到0并继续读取.

您可以完全控制内存,不会像在LinkedList中那样进行额外的节点分配,也不会像在ArrayList中那样调整大小.

一旦达到极限,旧对象就会自动释放.

你的要求

• 没有DB - 完成,只使用了一个数组

• 对象是相同的类型 - 简单模板

• 每秒最多50,000个对象 - 如果一个数组无法处理它,Java中没有任何东西可以

• 性能很重要 - 如上所述,访问整个列表中的数组快速迭代没有额外的开销很重要 - 尽可能快地迭代

• 随机访问也很重要 - 数据是有序的,并且/ after之后nextPutIndex的第一个非null元素是第一个可用的