15

我有一个程序，我需要在尽可能短的时间内（以毫秒为单位）对类似列表的对象进行 100,000 到 1,000,000 次随机访问读取，以用于类似元胞自动机的程序。我认为我正在使用的更新算法已经过优化（有效地跟踪活动单元等）。列表确实需要更改大小，但性能并不那么重要。因此，我想知道在如此短的时间内处理如此多的读取时，使用 Arrays 而不是 ArrayLists 的性能是否足以产生影响。目前，我正在使用 ArrayLists。

编辑：我忘了提：我只是存储整数，所以另一个因素是使用整数包装类（在 ArrayLists 的情况下）与 int （在数组的情况下）。有谁知道使用 ArrayList 是否实际上需要 3 个指针查找（一个用于 ArrayList，一个用于底层数组，一个用于 Integer->int），因为数组只需要 1 个（数组地址+特定的偏移量诠释）？HotSpot 会优化额外的查找吗？这些额外的查找有多重要？

Edit2：另外，我忘了提到我还需要进行随机访问写入（写入，而不是插入）。

4

12 回答 12

11

既然您已经提到您的数组实际上是原始类型的数组，请考虑使用Trove库中的原始类型集合类。

@viking 报告了在他的应用程序中使用 Trove 的显着（十倍！）加速 - 请参阅评论。另一方面，Trove 集合类型与 Java 的标准集合 API 类型不兼容。所以 Trove（或类似的库）不会在所有情况下都是答案。

于 2009-07-26T01:55:29.153 回答
10

尝试两者，但测量。

很可能您可以将某些东西组合在一起以使内部循环使用数组而无需更改所有代码。我怀疑 HotSpot 已经内联了方法调用，您将看不到性能提升。

另外，尝试 Java 6 update 14 并使用 -XX:+DoEscapeAnalysis

于 2009-07-25T20:15:57.513 回答
3

ArrayLists 比 Arrays 慢，但大多数人认为差异很小。但是，在您的情况下可能很重要，因为您要处理成千上万的人。

顺便说一句，重复：Java 中的数组或列表。哪个更快？

于 2009-07-25T19:56:35.880 回答
3

我会接受凯文的建议。

如果您的程序要将其与带有数组的版本进行比较，请先保留列表并衡量您的性能。如果这给您带来了可衡量的性能提升，请使用数组，如果不保留列表，因为它们会让您的生活更轻松。

于 2009-07-25T20:20:50.247 回答
3

使用 anArrayList而不是数组会产生开销，但它很可能很小。事实上，有用的数据位ArrayList可以存储在寄存器中，尽管您可能会使用更多（List例如 size）。

您在编辑中提到您正在使用包装器对象。这些确实有很大的不同。如果您通常重复使用相同的值，那么合理的缓存策略可能会很有用（Integer.valueOf对于 -128 到 128 给出相同的结果）。对于原语，原语数组通常会轻松获胜。

作为一种改进，您可能希望确保相邻的单元格在数组中往往是相邻的（您可以做得比具有空间填充曲线的列的行更好）。

于 2009-07-26T00:36:56.217 回答
2

一种可能性是重新实现 ArrayList（这并不难），但通过锁定/释放调用周期公开支持数组。这为您的写入提供了便利，但为您预先知道的大量读/写操作公开了数组，这些操作不会影响数组大小。如果列表被锁定，则不允许添加/删除 - 只需获取/设置。

例如：

  SomeObj[] directArray = myArrayList.lockArray();
  try{
    // myArrayList.add(), delete() would throw an illegal state exception
    for (int i = 0; i < 50000; i++){
      directArray[i] += 1;
    }
  } finally {
    myArrayList.unlockArray();
  }

这种方法继续封装 ArrayList 的数组增长/etc... 行为。

于 2009-07-25T20:27:29.907 回答
2

Java 对其对象使用双重间接，因此它们可以在内存中移动并且其引用仍然有效，这意味着每次引用查找都等效于两次指针查找。这些额外的查找无法完全优化掉。

也许更糟糕的是你的缓存性能会很糟糕。访问缓存中的值将比访问主内存中的值快很多倍。（可能是 10 倍）如果你有一个 int[]，你就知道这些值在内存中是连续的，因此很容易加载到缓存中。但是，对于 Integer[]，Integers 单个对象可能会随机出现在您的内存中，并且更有可能是缓存未命中。整数也使用 24 字节，这意味着它们比 4 字节值更不可能适合您的缓存。

如果你更新一个 Integer，这通常会导致创建一个新对象，这比更新一个 int 值要多几个数量级。

于 2009-07-25T22:27:35.453 回答
2

如果您只创建一次列表，并从中读取数千次，则 ArrayList 的开销可能很小，可以忽略不计。如果您要创建数千个列表，请使用标准数组。循环中的对象创建很快就会变成二次方，这仅仅是因为实例化成员变量、调用继承链上的构造函数等的所有开销。

因此——为了回答你的第二个问题——坚持使用标准整数而不是整数类。分析两者，您将很快（或者更确切地说，慢慢地）了解原因。

于 2009-07-26T00:57:25.987 回答
1

如果您不打算从这个结构中读取更多内容，那么请继续使用数组，因为按索引读取时会更快。

但是，请考虑您将如何在其中获取数据，以及排序、插入、删除等是否是一个问题。如果是这样，您可能需要考虑其他基于集合的结构。

于 2009-07-25T19:58:19.217 回答
1

基元要快得多（多得多）。总是。即使使用 JIT 转义分析等。跳过在 java.lang.Integer 中包装的东西。此外，跳过大多数 ArrayList 实现对 get(int) 所做的数组边界检查。大多数 JIT 可以识别简单的循环模式并删除循环，但如果您担心性能，则没有太多理由这样做。

您不必自己编写原始访问代码 - 我敢打赌，您可以转而使用 COLT 库中的 IntArrayList - 请参阅http://acs.lbl.gov/~hoschek/colt/ - “Colt 提供了一组用于 Java 中高性能科学和技术计算的开源库”）——只需几分钟的重构。

于 2009-07-26T07:32:37.620 回答
1

选项有：
1. 使用数组
2. 使用内部使用数组的 ArrayList

很明显 ArrayList 引入了一些开销（查看 ArrayList 源代码）。对于 99% 的用例，这种开销很容易被忽略。但是，如果您实现时间敏感算法并按索引从列表中读取数千万次，那么使用裸数组而不是列表应该会显着节省时间。使用常识。

请看这里：http ://robaustin.wikidot.com/how-does-the-performance-of-arraylist-compare-to-array我会亲自调整测试以避免编译器优化，例如我会改变“j = " 进入 "j += "，随后在循环后使用 "j"。

于 2012-01-05T17:11:09.673 回答
0

数组会更快，因为它至少会跳过函数调用（即 get(i)）。

如果你有一个静态大小，那么数组是你的朋友。

于 2009-07-25T19:56:13.323 回答