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

Question

使用Java。

我记录一些小对象用于一些计算等，我只需要最后 x 千个。所以我想将第一个释放给垃圾收集器。但是因为从 ArrayLists 中删除是昂贵的......

以下很重要(不能改)

• 没有数据库
• 对象是同一类型
• 每秒最多 50,000 个对象
• 性能很重要
• 快速遍历整个列表很重要
• 随机访问也很重要

这是可以改变的:

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

我的猜测:

• 链表
• 环形缓冲区
• ???

我怎样才能快速迭代并同时快速释放旧对象？

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 那样调整大小。

旧对象会在您达到限制后自动释放。

您的要求

• 没有数据库 -- 完成了，只是使用了一个数组

• 对象是同一类型——简单模板

• 每秒最多 50,000 个对象——如果一个数组不能处理它，Java 中的任何东西都不能处理

• 性能很重要 -- 如上所述，访问数组时没有额外的开销快速遍历整个列表很重要——尽可能快地进行迭代

• 随机访问也很重要——数据是有序的，nextPutIndex 处/之后的第一个非空元素是第一个可用的