如何在内存方面"organize"四叉树叶的数据结构？

Question

我有一个.hgt文件，它包含（1201x1201）16位整数。我将这个文件存储在四叉树中，最高级别为5。在第5层的叶子上，我有点的数组列表：

public class Point {
    short x,y,v;
}

x、 y-协调，v-高程。

一切正常，但它需要太多内存，因为我正在创建1201x1201=cca 1.44M的对象。我正在开发移动应用程序（Android），所以这是个问题，因为插入所有点数需要20秒以上，而且它"吃掉"了所有内存。有办法减少这种情况吗？

堆大小：49.258 MB

已分配：44.733 MB

数据对象：（计数：1 477 454），（总大小：34.081 MB）

hgt文件格式

Answer 1

我不是JVM专家，但上次我检查Java对象是否有8字节（64位）的元数据，这些元数据似乎也需要64位对齐。在32位的Android设备上可能会有所不同，但根据我的发现，Point对象需要16个字节，而不是6个字节，就像这样：

public class Point {
    // 8 byte metadata
    // 6 bytes of data.
    short x,y,v;
    // 2 bytes of padding for alignment of metadata.
}

达到这种效果的东西。因此，这大约是3个16位shorts最佳所需内存使用量的2.67倍。因此，一种将点的内存减少到一半以下并提高参考位置的解决方案是将所有内容存储在一个或多个巨大的short阵列中，如：

short xyz[num_points * 3];

这将需要非常、非常、非常接近最佳的内存量（在这种情况下，存储数组的一些元数据（如其长度）只需要最少量的开销，这绝对是微不足道的）。

也就是说，假设Point是16字节，这只解释了大约一半的爆炸性内存使用量（大约23兆字节）。另一个很可能是四叉树节点本身。尽管如此，如果使用上述技术，您可以将其从23兆字节减少到8.6兆字节。

对于剩余的内存使用，我的首要建议是避免为每个叶节点存储单独的ArrayList。比如说，你可以存储一个大数组列表中第一个点的索引（整个树只有一个），也可以再存储一个整数来表示该叶中存储的元素数量。这是一个C型伪代码示例，但您应该能够将四叉树节点至少设置为这样的节点：

struct QuadTreeNode
{
     // Stores AABB.
     float x1, x2, y1, y2;
     // Stores first child or -1 if empty.     
     int first_child;
     // Stores first element or -1 if this is not a leaf.
     int first_element;
};
struct QuadTree
{
     // Stores all the nodes in the quad tree. The 4
     // children of a node are stored contiguously.
     QuadTreeNode nodes[];
     // Stores all the elements in the quad tree. The
     // elements at the leaves are stored contiguously.
     Element elements[];
};

这甚至不是很紧凑，但它相当紧凑。