java - 具有大量变异的矩阵的最佳数据结构

Question

我很难想出一个有效的数据结构来保存矩阵(它们的大小可能接近 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 一样。

有什么关于数据结构的建议可以满足这个目的吗？

Answer 1

对于稀疏数组，HashMap是一个很好的选择。比较快- O(1)查找 - 并且相对节省空间。我说相对是因为有很多开销。

还有其他Map具有不同行为的实现 - 例如 TreeMap在 O(lg n) 中执行但按键排序。

所以同时 Map<Integer, Map<Integer, Integer>>或类似的，可能会用 100x100 为您节省空间非常稀疏的矩阵，我想一个 int[][]效率不会低很多。

如果性能是一个问题，您绝对应该使用类似 jmh 的方法对替代方案进行基准测试.我希望 int[][]胜过Map大多数情况下基于解决方案。

如果您使用的是 Guava，则可以使用 Table .我上面描述的两个备选方案本质上是 HashBasedTable 和 ArrayTable .我不希望 ArrayTable比原始 int[][] 慢得多, 但会占用更多空间。

简而言之:

1. 基准
2. 基准
3. 基准