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

Question

我有困难想到一个有效的数据结构来保存矩阵（它们可以接近75x75的大小）。1是唯一重要的单元格，0始终为空且无用。此外，我希望我们可以不将0加载到数据结构中。

---

        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

请记住，我将制作一个算法来对这个矩阵进行排序，其中我将移动许多列和行。

我考虑使用行、列和值的表格。但我不确定这是否是最好的选择。我的老师告诉我要看看图形结构；它看起来很有前途，可以保存数据，但移动行和列对我来说像地狱一样。

有没有适合这个目的的数据结构的建议？

- legopiraat

---

也许这对你有用： https://code.google.com/p/efficient-java-matrix-library/ - heaphach

@heaphach，你链接中的第一行是“是一个用于操作密集矩阵的线性代数库”。重点在于“密集”。 - Boris the Spider

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. 测试性能

- Boris the Spider

---

我认为你应该澄清你的意思是HashMaps。还有其他具有不同运行时行为的Maps。顺便说一句，HashMaps可以通过初始化大小来优化空间使用。 - LastFreeNickname

@LastFreeNickname 完成。为了优化空间，您需要设置大小和负载因子。这并不能解决速度问题 - 可能比数组访问更慢。但是，OP需要进行基准测试以确定速度差异是否超过内存差异。 - Boris the Spider

@BoristheSpider非常感谢您提供的基准库，我刚刚建立了一个项目，以便能够对任何可能的解决方案进行基准测试，谢谢！ - legopiraat