java - 如何在内存方面为四叉树叶的 "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 file format

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-ish 伪代码示例，但您应该能够使您的四叉树节点至少像这样:

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[];
};

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