Ree*_*d B 8 java data-structures
我有一个大的2D网格,x-by-y.应用程序的用户将添加有关此网格上特定点的数据.遗憾的是,网格太大而无法实现为大型x-by-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();" 设置一个点然后通过散列找到Point来查找索引.然而,问题是数组必须是散列函数范围的大小.如果此范围小于添加的数据点总数,则它们将没有空间或必须添加到溢出.因为我不知道将要添加的点数,所以我必须假设这个数字小于一定数量,然后将数组设置为该大小.同样,这实例化了一个非常大的数组(尽管假设数据点的数量比x*y少,但比原来要小).
看起来我想要的是SparseArray,正如一些人所提到的那样.它们的实施方式类似于在BST内部使用BST吗？
Edit2:Map <>是一个界面.如果我使用Map,那么看起来TreeMap <>将是最好的选择.所以我最终会得到TreeMap <TreeMap <Point >>,类似于人们所做的Map <Map <Point >>>建议,这基本上是BST内部的BST.感谢您的信息,因为我不知道TreeMap <>基本上是BST的Java SDK.
编辑3:对于那些可能关心的人,选择的答案是最好的方法.首先,必须创建一个包含(x,y)并实现可比较的Point类.Point可以通过类似(((long)x)<< 32)+ y)的方式进行比较.然后,TreeMap会指向数据.搜索这个是有效的,因为它在一个平衡的树中,因此log(n)成本.用户还可以使用TreeMap.entrySet()函数查询所有这些数据,或者遍历它,该函数返回一组Points以及数据.
总之,这允许稀疏阵列的空间效率和搜索效率的实现,或者在我的情况下,2D阵列,其也可以有效地迭代.
将大点阵列的索引存储到其中一个空间结构中.如果数据不是均匀分布的,则这种空间结构是有利的,例如集中在城市中的地理数据,并且在海中没有任何意义.
想想你是否可以忘记常规网格,并使用四叉树.
(想想,为什么你需要一个规则的网格？常规网格通常只是一个简化)
在任何情况下都不要使用Objects来存储Point.这样的Object只需要20个字节,因为它是一个对象!对于庞大的数据集来说,这是个坏主意.
An int x[],和int[] y/或int[]xy数组是与内存使用相关的理想选择.
考虑阅读
Hanan Samet的 "多维数据结构的基础"
(至少是介绍).
您可以使用 aMap<Pair, Whatever>来存储数据（您必须编写 Pair 类）。如果您需要以某种特定顺序迭代数据，请进行 PairComparable并使用NavigableMap
| 归档时间： |
|
| 查看次数： |
3140 次 |
| 最近记录： |