保持项目彼此位置关系的三维数据结构

Question

我有一个关于数据结构的作业，prof希望我们在项目中使用不同类型的DS，但我不知道他的意思是（一种将项目保持相互位置关系的三维数据结构。数据结构中的每个单元格都可以容纳多个项目。） 我尝试了对象的 Arraylists、对象队列！知道我可以尝试哪种 DS 来节省我的时间吗？

Answer 1

最简单的空间数据结构是 3D 数组。在 java 中，您可以创建一个如下：

Object[][][] my3DArray = new Object[10][10][10];

在这里，您可以存储 10*10*10=1000 个彼此空间关系的对象。不幸的是，每个维度只有 10 个可能的坐标。

如果您想要更高效的东西，请寻找四叉树/八叉树、kd 树（如@BeyelerStudios 在评论中提到的）、R 树、LSH（局部敏感哈希）甚至空间填充曲线（Z 曲线、希尔伯特曲线） ，……）。这些只是主要的系列，每种类型的 DS 都有许多版本。

编辑以回答评论。除了 3D 阵列方法，上述所有解决方案都非常节省空间。空间效率最高的可能是PH-Tree（一种四叉树，由我自己开发），在某些情况下，它可能需要比普通坐标数组更少的内存。不幸的是，它的理解和实现相对复杂。

如果要使用一维排序方案，例如数组或列表，请尝试使用空间填充曲线。Z 曲线可能是最简单的。使用空间填充曲线，您可以为空间中的每个点计算一个“关键”（z-key 或 Morton-number），然后在数组或列表中对它们进行排序。在这样的有序列表/数组中，直接邻居也可能（但不保证）在 3D 空间中接近。相反，在 3D 空间中接近的点往往（但不能保证）在列表/数组中接近。

对于整数坐标，可以通过交错坐标位来计算z 键（也称为MortonNumber）。您也可以对浮点值执行此操作，但您需要小心处理负值，否则您可能会在正值和负值之间产生裂痕。

Answer 2

如果你被允许使用 Guava，那么我会考虑一个Multimap的MyObjindexed by XyzCoord，其中XyzCoord是一个自定义对象来保存三个位置数字，并且MyObj是你希望在不同坐标处存储一个或多个的自定义对象。

避免番石榴，您可以使用标准Map的List<MyObj>。它也可以由List<Integer>长度为 3 的哪个索引。

事实上，有很多很多方法可以做到这一点。因此，您的问题可能有点过于宽泛。再看一下集合类，如果您不知道它们是如何使用的，请尝试询问有关每个类的具体问题。