9

我有一个大的 2D 网格，x-by-y。应用程序的用户将添加有关此网格上特定点的数据。不幸的是，网格太大而无法实现为大型 x×y 数组，因为运行它的系统没有足够的内存。

什么是实现这一点的好方法，以便只有添加了数据的点才存储在内存中？

我的第一个想法是创建数据点的 BST。诸如“(long)x<<32 + y”之类的散列函数将用于比较节点。

然后我得出结论，如果不平衡，这可能会降低效率，所以我想出了一个由可比较的 BST 分数组成的 BST 的想法。外部 BST 将根据 x 值比较内部 BST。内部 BST 将通过它们的 y 值来比较这些点（并且它们都将具有相同的 x）。因此，当程序员想要查看 (5,6) 处是否有一个点时，他们会在外部 BST 中查询 5。如果在该点存在内部 BST，那么程序员将在内部 BST 中查询 6。结果将被退回。

你能想出更好的方法来实现它吗？

编辑：关于 HashMaps：大多数 HashMaps 需要有一个用于查找的数组。有人会说“data[hash(Point)] = Point();” 设置一个点，然后通过散列找到该点以找到索引。然而，问题是数组必须是散列函数范围的大小。如果此范围小于添加的数据点总数，则它们将没有空间或必须添加到溢出中。因为我不知道要添加的点数，所以我必须假设这个数字会小于某个数量，然后将数组设置为该大小。同样，这会实例化一个非常大的数组（尽管如果假设数据点将少于 x*y，则它比最初的要小）。

正如一些人所提到的，看起来我想要的是一个 SparseArray。它们的实现方式是否类似于在 BST 中包含 BST？

Edit2: Map<> 是一个接口。如果我要使用地图，那么看起来 TreeMap<> 将是最好的选择。所以我最终会得到 TreeMap< TreeMap< Point> >，类似于人们提出的 Map< Map< Point> > 建议，这基本上是 BST 中的 BST。不过，感谢您提供的信息，因为我不知道 TreeMap<> 基本上是 BST 的 Java SDK。

Edit3：对于那些可能关心的人，选择的答案是最好的方法。首先，必须创建一个包含 (x,y) 并实现可比较的 Point 类。该点可能会通过类似 (((long)x)<<32)+y) 进行比较。然后将 TreeMap 每个点指向数据。搜索它是有效的，因为它位于平衡树中，因此 log(n) 成本。用户还可以使用 TreeMap.entrySet() 函数查询所有这些数据，或遍历这些数据，该函数返回一组点以及数据。

总之，这允许稀疏数组的空间高效和搜索高效的实现，或者在我的情况下，二维数组也可以有效地迭代。

4

8 回答 8

7

Quadtree 、k -d-tree或R -tree。

将大点数组的索引存储到空间结构之一中。如果数据分布不均，这种空间结构是有利的，例如集中在城市中的地理数据，并且在海洋中没有意义。

想想您是否可以忘记常规网格，并继续使用四叉树。
（想一想，为什么需要规则网格？规则网格通常只是一种简化）

在任何情况下都不要使用对象来存储点。这样的对象只需要 20 个字节，因为它是一个对象！对于庞大的数据集来说是个坏主意。

一个int x[], 和int[] y, 或一个int[]xy数组是与内存使用相关的理想选择。

考虑阅读

Hanan Samet的 “多维数据结构基础”

（至少是引言）。

于 2013-06-21T16:12:17.870 回答
4

您可以使用 aMap<Pair, Whatever>来存储您的数据（您必须编写 Pair 类）。如果您需要按特定顺序迭代数据，请制作 PairComparable并使用NavigableMap

于 2013-06-21T16:11:12.043 回答
2

一种方法可能是Map<Integer, Map<Integer, Data>>. 外层映射的键是行值，内层映射的键是列值。与该内部映射（Data在本例中为类型）关联的值对应于 处的数据(row, column)。当然，如果您正在考虑尝试进行矩阵运算等，这将无济于事。为此，您需要稀疏矩阵。

另一种方法是将行和列表示为一个Coordinate类或一个Point类。您将需要实现equals和hashCode（应该非常简单）。然后，您可以将数据表示为Map<Point, Data>或Map<Coordinate, Data>。

于 2013-06-21T16:11:26.073 回答
1

您可以有一个对象列表的列表，并且该对象可以编码它的水平和垂直位置。

class MyClass
{
    int x;
    int y;
    ...
}
于 2013-06-21T16:11:04.793 回答
0

也许我在这里太简单了，但我认为你可以使用常规的HashMap. 它将包含自定义Point对象作为键：

class Point {
    int x;
    int y;
}

然后你重写 equals 方法（以及 hashCode 方法）以基于xand y。这样你只存储有一些数据的点。

于 2013-06-21T16:11:13.497 回答
0

我认为您在正确的轨道上以一种内存有效的方式执行此操作 - 它可以通过使用映射的映射来相当容易地实现，包装在一个类中以提供一个干净的查找接口。

另一种（并且内存效率更高）的方法是使用单个映射，其中键是元组 (x,y)。但是，如果您需要进行诸如“给我所有值”之类的查询，这将不太方便x == some value。

于 2013-06-21T16:11:16.983 回答
0

您可能想查看Matrix 工具包项目中的 FlexCompColMatrix、CompColMatrix 和其他稀疏矩阵实现。

性能实际上取决于写入/读取比率和矩阵的密度，但是如果您使用的是矩阵包，则通过切换实现来进行实验会更容易

于 2013-06-21T16:13:28.560 回答
0

我对您的建议是使用Commons Math: The Apache Commons Mathematics Library。因为它将通过利用您的应用程序所需的数学力量来节省您的时间。

于 2013-06-21T17:08:18.813 回答