Mat*_*iak 5 java data-structures
在Java中编写二维网格块时使用的最佳数据结构是什么？网格上的平铺应该可以通过它们的位置轻松引用,以便可以有效地计算邻居和路径.它应该是2D阵列吗？一个ArrayList？别的什么？
如果你不太担心速度或内存,你可以简单地使用2D数组 - 这应该足够好.
如果速度和/或内存是您的问题,那么这取决于内存使用情况和访问模式.
如果您需要高性能,则可以使用单维数组.您将正确的索引计算为y * wdt + x.这有两个潜在的问题:缓存未命中和内存使用.
如果您知道您的访问模式大部分时间都在获取元素的邻居,那么如上所述将2D空间映射到1D数组可能会导致缓存未命中 - 您希望邻居在内存中关闭,并且邻居从2个不同的行不是.您可能必须以不同的顺序将2d图块映射到1d阵列.例如,见希尔伯特曲线.
为了更好地使用内存,如果您知道大多数切片始终相同(例如始终为草),则可能需要实现稀疏数组或四叉树.两者都可以非常有效地实现,并考虑到缓存感知(稀疏数组链接就是这方面的好例子).另一个好处是可以动态扩展这些.但是,您最终必须支付额外的间接级别才能使其正常工作.
注意:HashMap如果您担心性能,请小心使用诸如s之类的通用类,其中键类型是基本类型或特殊位置类 - 每次索引哈希映射或支付时,您将不得不分配对象拳击/拆箱的价格.除此之外,哈希映射将不允许您进行有效的空间查询(例如,给出我在给定对象的半径R中存在的所有对象 - 四叉树对此更好).
| 归档时间： |
|
| 查看次数： |
5479 次 |
| 最近记录： |