结构数组或数组结构？

嗯。 我有一个表，这是一个我需要用Java存储的结构数组。 天真的不用担心内存的方法说这样做：

public class Record { final private int field1; final private int field2; final private long field3; /* constructor & accessors here */ } List records = new ArrayList(); 

如果我最终使用大量（> 10 ⁶ ）记录，偶尔访问个别记录，一次一个，我怎么能弄清楚前面的方法（ArrayList）如何与优化的存储成本方法进行比较：

 public class OptimizedRecordStore { final private int[] field1; final private int[] field2; final private long[] field3; Record getRecord(int i) { return new Record(field1[i],field2[i],field3[i]); } /* constructor and other accessors & methods */ } 

编辑：

• 假设记录数是不经常更改或从不更改的内容
• 我可能不会使用OptimizedRecordStore方法，但我想了解存储成本问题，以便我可以放心地做出决定。
• 显然，如果我在上面的OptimizedRecordStore方法中添加/更改记录数，我要么必须用新的对象替换整个对象，要么删除“final”关键字。
• kd304提出了一个在我脑海中的好点。 在与此类似的其他情况下，我需要对记录进行列访问，例如，如果field1和field2是“time”和“position”，那么将这些值作为数组用于MATLAB非常重要，因此我可以绘制图形/有效地分析它们。

Answer 1

在这种情况下，给出通用“在必要时进行优化”的答案是无益的，因为恕我直言，程序员应该始终意识到设计选择中不同的性能，当选择导致性能损失一个数量级时，特别是API编写者。

最初的问题非常有效，我倾向于同意第二种方法更好，因为他的具体情况。 我已经编写了图像处理代码，其中每个像素需要一个数据结构，这种情况与此不太相似，除了我需要频繁随机访问每个像素。 为每个像素创建一个对象的开销是巨大的。

Answer 2

第二个版本更糟糕 。 执行插入或删除时，不是调整一个数组的大小，而是调整三个数组的大小。 更重要的是，第二个版本将导致创建更多临时对象，并且它将在访问时执行。 这可能会导致大量垃圾（从GC的角度来看）。 不好。

一般来说，在考虑性能之前，您应该担心如何使用对象。 所以你有一个包含三个字段或三个数组的记录。 哪一个更准确地描绘了你的建模？ 我的意思是，当你插入或删除一个项目时，你是在做三个数组中的一个还是三个作为一个块？

我怀疑是后者，在这种情况下，前者更有意义。

如果您真的关心插入/删除性能，那么可能需要使用不同的数据结构，可能是SortedSet或Map或SortedMap。

Answer 3

如果您有数百万条记录，第二种方法有几个优点：

• 内存使用 ：第一种方法使用更多内存，因为a）堆中的每个Java对象都有一个头（包含类id，锁状态等）; b）对象在内存中对齐; c）对对象的每个引用花费4个字节（在具有压缩OOP或32位JVM的64位JVM上）或8个字节（没有压缩OOP的64位JVM）。 有关详细信息，请参阅CompressedOops 。 因此，第一种方法需要大约两倍的内存（更准确地说：根据我的基准测试，一个16字节有效负载的对象+对它的引用在32位Java 7上占用28个字节，在64位Java 7上占用36个字节压缩OOP，在64位Java 7 w / o压缩OOP上40字节）。
• 垃圾收集 ：虽然第二种方法似乎创建了许多对象（每次调用getRecord时都有一个），但可能不是这样，因为现代服务器JVM（例如Oracle的Java 7）可以应用转义分析和堆栈分配来避免临时堆分配在某些情况下的对象; 无论如何，GCing短期物品很便宜。 另一方面，如果没有数百万个长期存在的对象（如第一种方法中那样）可检查的可达性（或者至少这些对象可能会使您的应用程序需要更加小心），垃圾收集器可能更容易调整GC生成大小）。 因此，第二种方法可能更适合GC性能。 但是，要想看它是否会对实际情况产生影响，就应该自己做一个基准测试。
• 序列化速度 ：（de）序列化磁盘上大量原语的速度仅受HDD速度的限制; 序列化许多小对象不可避免地会更慢（特别是如果你使用Java的默认序列化）。

因此，我经常对非常大的集合使用第二种方法。 但是，当然，如果你有足够的内存并且不关心序列化，那么第一种方法就更简单了。

Answer 4

你打算如何访问数据？ 如果对字段的访问总是耦合，那么使用第一个选项，如果您要自己处理字段，那么第二个选项更好。

请参阅维基百科： Parallel Array中的这篇文章

关于何时使用单独数组更方便的一个很好的例子可以是模拟，其中数值数据被打包在同一个数组中，以及其他属性，如名称，颜色等，只是为了在其他数组中呈现数据而被访问。

Answer 5

我很好奇，所以我实际上运行了一个基准。 如果你没有像[1]那样重新创建对象，那么SoA将AoS击败5-100％，具体取决于工作负载[2]。 在这里查看我的代码：

https://gist.github.com/twolfe18/8168262c5420c7a62d39

[1]我没有补充说，因为如果你足够关注速度来考虑这个重构，那么这样做会很愚蠢。

[2]这也不考虑重新分配，但同样，这通常是你可以摊还或静态知道的东西。 这是纯速度基准的合理假设。

Answer 6

请注意，第二种方法可能会对缓存行为产生负面影响。 如果您想一次访问一条记录，最好不要将该记录分散到整个地方。

此外，您在第二种方法中获得的唯一记忆是（可能）由于成员对齐。 （并且必须分配一个单独的对象）。 否则，它们具有完全相同的内存使用，渐近。 由于地方性，IMO的第一个选择要好得多

Answer 7

每当我尝试在Java中进行数字运算时，我总是不得不恢复到C风格的编码（即接近你的选项2）。 它最大限度地减少了系统中浮动的对象数量，而不是1,000,000个对象，你只有3个。我能够使用C风格对实时声音数据进行一些FFT分析，它也是如此使用对象慢。

Answer 8

我会选择第一种方法（结构数组）， 除非你相对不经常访问商店并且遇到严重的内存压力问题。

第一个版本基本上以“自然”forms存储对象（+1 BTW用于使用不可变记录）。 由于每个对象的开销（可能大约8-16个字节，具体取决于您的JVM），这会占用更多的内存，但是只需一个简单的步骤，就可以以方便且易于理解的forms访问和返回对象。

第二个版本总体上使用较少的内存，但是在每个“获取”上分配新对象是一个非常难看的解决方案，如果访问频繁，则无法很好地执行。

其他一些可能的考虑因素：

一个有趣的“极端”变体是采用第二个版本，但编写您的算法/访问方法直接与底层数组交互。 这显然会导致复杂的相互依赖性和一些丑陋的代码，但如果你真的需要它可能会给你绝对最好的性能。 将此方法用于密集图形应用程序（例如操纵大量3D坐标）是很常见的。

“混合”选项将在第二个版本中将基础数据存储在数组结构中，但是将访问的对象缓存在HashMap中，以便您只在第一次访问特定索引时生成对象。 如果只有一小部分对象可能被访问，那么可能有意义，但所有数据都需要“以防万一”。

Answer 9

（不是直接的答案，但我认为应该给出一个答案）

从你的评论，

“cletus – 我非常尊重你的想法和意见，但你给了我高级编程和软件设计观点，这不是我正在寻找的。我无法学会忽视优化，直到我能够获得直观的感觉不同实施方式的成本，和/或估计这些成本的能力。 – Jason S 2009年7月14日14:27“

您应该始终忽略优化，直到它出现问题为止。 最重要的是让系统可供开发人员使用（因此他们可以让用户使用它）。 很少有人会关注自己的优化，事实上在大约20年的专业编码中，我总是关心优化两次：

1. 编写一个主要目的是比另一个产品更快的程序
2. 编写智能手机应用程序旨在减少客户端和服务器之间发送的数据量

在第一种情况下，我写了一些代码，然后通过分析器运行它，当我想做某事时我不确定哪种方法最好（对于速度/内存）我会编写一种方式并在分析器中查看结果，然后用另一种方式编码并查看结果。 然后我会选择两者中较快的一个。 这有效，你可以学到很多关于低级别决策的知识。 但是，我没有让它影响更高级别的课程。

在第二种情况下，没有涉及编程，但我做了相同的基本事情，查看正在发送的数据，并弄清楚如何减少发送的消息数量以及发送的字节数。

如果您的代码清晰，那么一旦发现它很慢就会更容易加速。 正如Cletus在他的回答中所说，你正在调整一次-vs-三次……一次将比三次更快。 从更高的角度来看，一次比三次更容易理解，因此更可能是正确的。

就个人而言，我宁愿慢慢得到正确的答案，然后迅速得到错误的答案。 一旦我知道如何得到正确答案，那么我就可以找到系统速度慢的地方，并用更快的实现来替换它的那些部分。

Answer 10

因为你正在使int []字段成为最终的，所以你只需要对数组进行一次初始化即可。 因此，如果你想要10 ^ 6 field1，那么Java需要为每个int []分隔那么多内存，因为你无法重新分配这些数组的大小。 使用ArrayList，如果您事先不知道记录数并且可能会删除记录，则可以预先节省大量空间，然后在删除记录时也可以保存。

Answer 11

我也会选择ArrayList版本，所以我不需要担心增长它。 您是否需要一个像访问值的列？ 您的问题背后的情况是什么？

编辑您也可以使用常用的long[][]矩阵。 我不知道你是如何将列传递给Matlab的，但我猜你在基于列的存储中没有获得太多的速度，更有可能是你在java计算中失去了速度。