结构数组或数组结构？

Question

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

public class Record {
  final private int field1;
  final private int field2;
  final private long field3;
  /* constructor & accessors here */
}

List<Record> records = new ArrayList<Record>();

如果我最终使用大量(> 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

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

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