5

使用Java。

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

以下是重要的（不能改变）

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

这可以改变：

  • 现在使用ArrayList<MyObject>
  • 限制：100,000 个对象（停止记录，但必须继续）

我的猜测：

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

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

4

3 回答 3

5

一个办法

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

  • 单一分配

  • 没有获取/放置/等。内联的方法开销

  • 简单的

一个示例（可能无法编译，即时编写）实现：

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是第一个可用的

于 2013-04-17T10:09:01.567 回答
3

在不知道您的任何其他要求的情况下，某种类型的链表似乎是合适的。只需跟踪第一个元素（列表中的“头部”）和最后一个元素（“尾部”）。每个链接的元素引用下一个。添加到尾部，并从头部移除。

添加和删​​除将非常快（O(1)），并且迭代也将非常简单。

但是，如果您需要随机访问元素，则此解决方案的性能会很差。

编辑

由于您已添加需要随机访问，因此链接列表将不起作用。如果在任何给定时间的最大对象数是固定的，您可以使用一个ArrayList（或一个基本的 Java 数组）并将其视为一个环绕缓冲区。到达末尾后，从头开始替换对象，并跟踪表示列表逻辑开始的索引。（如果您使用基本数组，您还需要跟踪缓冲区中当前有多少元素——相当于List.size()）。

当您在缓冲区的开头替换对象时，旧对象将被自动释放并被垃圾收集（只要它们没有在其他地方引用）。

于 2013-04-17T09:55:26.847 回答
3

我会使用一个数组，并实现一个 RingBuffer。我已经这样做了，但是使用了许多单元测试来确保它始终有效。我没有找到适合我需要的环形缓冲区，也许你有更多的运气。

于 2013-04-17T10:17:09.593 回答