我很难想出一个有效的数据结构
来保存矩阵(它们的大小可能接近 75x75)。 1 是唯一重要的单元格,0 将始终为空且无用。另外,如果我们不能将 0 加载到 data structure
中,我更愿意。
Col 1 Col 2 Col 3 Col 4 Col 5
Row 1 0 0 1 0 1
Row 2 0 1 0 0 0
Row 3 1 1 0 0 0
Row 4 0 0 0 0 0
Row 5 0 0 1 0 1
请记住,我将制定一个算法来对这个矩阵
进行排序,我将在其中移动大量的列和行。
我在考虑一个包含行、列和值的表格。但不确定这是否是最佳选择。我的老师让我看一个图形结构
;保存数据看起来很有希望,但移动行和列对我来说就像 hell 一样。
有什么关于数据结构
的建议可以满足这个目的吗?
最佳答案
对于稀疏数组,HashMap
是一个很好的选择。比较快- O(1)
查找 - 并且相对节省空间。我说相对是因为有很多开销。
还有其他Map
具有不同行为的实现 - 例如 TreeMap
在 O(lg n)
中执行但按键排序。
所以同时 Map<Integer, Map<Integer, Integer>>
或类似的,可能会用 100x100
为您节省空间非常稀疏的矩阵,我想一个 int[][]
效率不会低很多。
如果性能是一个问题,您绝对应该使用类似 jmh 的方法对替代方案进行基准测试.我希望 int[][]
胜过Map
大多数情况下基于解决方案。
如果您使用的是 Guava,则可以使用 Table
.我上面描述的两个备选方案本质上是 HashBasedTable
和 ArrayTable
.我不希望 ArrayTable
比原始 int[][]
慢得多, 但会占用更多空间。
简而言之:
- 基准
- 基准
- 基准
关于java - 具有大量变异的矩阵的最佳数据结构,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/28559442/