logo标签列表

用于存储二维数据的数据结构的想法？

javadata-structures
9
我有一个大的二维网格，x乘以y。应用程序的用户将添加有关此网格上特定点的数据。不幸的是，该网格太大，无法实现为大型x乘以y数组，因为运行这个系统的计算机没有足够的内存。
有什么好的方法可以实现这一点，以便只有添加了数据的点才存储在内存中？
我的第一个想法是创建数据点的二叉搜索树(BST)。比较节点将使用哈希函数"(long)x<<32 + y"。
然后我得出结论，如果不平衡，这可能会失去效率，因此我想到了一个类似于BST的可比较BST的想法来存储点。外部BST将根据其x值比较内部BST。内部BST将根据其y值（它们都具有相同的x）比较点。因此，当程序员想查看是否存在(5,6)点时，他们会查询外部BST以获取5。如果存在一个内部BST则程序员会为6查询内部BST。结果将被返回。
你能想到更好的实现方式吗？
编辑:关于HashMaps：大多数HashMaps需要具有用于查找的数组。例如"data[hash(Point)] = Point();"将设置一个点，然后通过对其进行哈希来查找Point以找到索引。问题在于，数组必须是哈希函数范围的大小。如果此范围小于添加的总数据点数，则它们将没有空间或必须添加到溢出中。因为我不知道将添加的点数，所以我必须假设这个数字将小于某个数量，然后将数组设置为该大小。再一次，这会实例化一个非常大的数组（虽然比最初的如果假设有更少的数据点，则规模更小）。我希望该结构能够随着数据量的增加而线性扩展，并且在为空时不占用大量内存。
看起来我想要的是一个稀疏数组，就像一些人已经提到的那样。它们是否类似于BST中的BST？
编辑2：Map<>是一个接口。如果我要使用Map，那么TreeMap<>似乎是最佳选择。因此，我将得到TreeMap>，类似于人们提出的Map>建议，即基本上是BST中的BST。感谢信息，因为我不知道TreeMap<>基本上是BST的Java SDK。
编辑3：对于那些关心的人，被选中的答案是最佳方法。首先，必须创建一个包含（x，y）并实现可比性的Point类。该点可能会被比较为像（（（长）x）<<32）+ y）。然后，每个点都将TreeMap到数据中。由于这是在平衡树中，所以搜索是有效的，成本为log（n）。用户还可以通过使用TreeMap.entrySet()函数查询所有这些数据或迭代它，该函数返回一组带有数据的点。
总之，这使得稀疏数组（在我的情况下为二维数组）的占用空间高效且搜索高效，同时也能够高效地进行迭代。
1
不要重复造轮子，看看空间数据结构。 - AlexWien
@Kiril Raychev：一旦这些点被添加，我计划使用结构中的所有数据进行计算，但不需要范围查询。 - Reed B
好的，看起来Map是你使用的最佳选择。但是当你遇到速度和空间问题时，请考虑使用基于非对象的HashMap，可以节省60％的内存空间。（点对象 vs 原始类型） - AlexWien
@AlexWien：如果我使用原始哈希映射，那么我必须将一个大数组推入堆栈，就像我的第一个编辑所解释的那样。从内存角度来看，这几乎与使用直接映射数组一样低效，因为两者都需要在启动时占用大量空间。如果映射是动态分配的，那么当点数较少时，我可以使用非常少的内存（但是，确实会有指针开销）。 - Reed B
只要你不解释你的操作，就不可能找到最佳结构。在Morton索引数组中具有点的B树也是可能的。或者是一组哈希映射的网格。 - AlexWien
显示剩余2条评论
8个回答
8

使用四叉树、k-d树或R树其中之一进行编程相关内容的存储。

将大型点数组的索引存储到这些空间结构中之一。如果数据不均匀分布，例如地理数据集中在城市而海洋中没有点，则这些空间结构是有优势的。

思考是否可以放弃常规网格，只使用四叉树。
（想一想，为什么需要常规网格？常规网格通常只是一种简化）

绝不能使用对象来存储一个点。 这样的对象只为了表示一个点就需要20个字节！对于大型数据集来说是个糟糕的想法。

int x[]和int[] y或int[]xy数组与内存使用相关方面最为理想。

考虑阅读

Hanan Samet的"多维数据结构基础"

（至少是介绍部分）。

@AndreaLigios，是的，与您以前的实现相比，使用这些工具可以将性能提高100到1000倍。 - AlexWien
这些是不错的结构，但四叉树并不是最好的选择，因为我的数据是按离散行和列排列而不是分布在二维连续域中的点，而这正是四叉树设计的目的。感谢您的回答！ - Reed B
四叉树并非为连续坐标而设计，而是为整数坐标而设计，通常是2的幂。因此是离散的。四叉树是一个索引，而不是存储本身。它用于以最小的努力找到附近的点。您可以将数据存储为点（行、列）或（x，y）。您的数据是否均匀分布或聚集在某些地方？ - AlexWien
我也推荐使用类似于这里提到的树形结构来保留空间相关性，而使用哈希表方法会丢失这些信息。 - Wildhammer
4

您可以使用Map<Pair, Whatever>来存储数据（您需要编写Pair类）。如果您需要按照某个特定顺序迭代数据，则可以使Pair Comparable，并使用NavigableMap

+1 好的解决方案；比我先了 :) 我也喜欢提到 NavigableMap。 - Vivin Paliath
为什么不直接使用Point类呢？ - splungebob
@splungebob 你是说 java.awt.Point 吗？我认为使用本来用于完全不同目的的类，只是因为它们具有正确的属性，总是一个坏主意。awt点是可变的，可以使用双精度数设置，并且可以应用变换-完全不符合我们在这里所需要的。 - jmruc
@KirilRaychev 我已经重新实现了Point类，以便在没有java.awt的嵌入式系统中使用。这比一开始看起来要更费力。 - AlexWien
那么，如果我想要遍历地图中的每个点而不检查每个潜在的映射，我可以使用TreeMap.keySet()函数获取所有键值的Set，然后遍历它们？ - Reed B
1
@ReedB 是的，你可以这样做。推荐的方法是迭代 entrySet 而不是 keySet，因为它更有效率，但两种方法都可以。 - jmruc
2

一种方法是使用 Map<Integer, Map<Integer, Data>>。外部映射的键是行值，内部映射中的键是列值。与该内部映射相关联的值（在本例中为类型为 Data 的值）对应于 (row, column) 处的数据。当然，如果您想尝试进行矩阵操作等操作，则这将无助于解决问题。对于此类问题，您需要使用稀疏矩阵。

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

1
你可以拥有一个对象列表的列表，并且该对象可以编码其水平和垂直位置。
class MyClass
{
    int x;
    int y;
    ...
}
但是，每次添加新对象时，因为我想要一个唯一的点集，我都必须搜索所有数据的列表，以查看它是否已经存在，然后更新数据点或添加新数据点。我试图避免这种低效的过程。 - Reed B
@ReedB 这并不是很低效，特别是如果你有一个列表的列表，外部列表对应于x，内部列表对应于y。搜索的时间复杂度将为**O(x+y)**。 - Sam I am says Reinstate Monica
0
也许我在这里过于简单化了，但我认为你可以只使用一个普通的 HashMap。它将包含自定义的 Point 对象作为键：
class Point {
    int x;
    int y;
}

然后你重写equals方法（因此也是hashCode方法），以基于x和y。这样，你只存储具有某些数据的点。

0

我认为你正在正确的轨道上以一种内存高效的方式来完成这个任务 - 可以通过使用一个嵌套映射的地图，再包装在一个类中，以便提供一个干净的接口进行查找。

另一种（更内存高效）的方法是使用单个映射，其中键是元组（x，y）。但是，如果您需要进行查询，例如“给我所有值，其中x ==某个值”，则这将不太方便。

地图的地图看起来很有前途。正如我在其他几个评论中所说的，如果我使用一个单独的 Map，它是 TreeMap，那么它必须基于从两点生成的某种哈希值来比较节点，就像我最初的想法一样使用单个 BST。如果这个 Map 是一个线性的 Map，比如一个列表，那么这将非常低效，因为每次我想要添加数据时，我都必须线性搜索列表，以查看它是否已经存在，然后更新它或者添加一个新的数据点。 - Reed B
0

你可能想要查看Matrix toolkit项目中的FlexCompColMatrix、CompColMatrix和其他稀疏矩阵实现。

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

0
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接