如何处理非常大的矩阵(例如1000000 × 1000000)

Question

我的问题很一般…而且也不重复…

当我们声明int mat[1000000][1000000];

时

它肯定会给出一个错误，说矩阵大小太大。

我在许多竞争性编程网站上看到过许多问题，我们需要声明一个具有10^6行，列的2d矩阵，我知道总是有一些技巧与之相关，以减少矩阵大小。

所以我只是想问在这种情况下我们可以使用什么可能的方法或技巧来最小化尺寸。我的意思是，通常需要哪种类型的算法来解决它，比如DP或其他人??

Answer 1

1. 在DP中，如果当前行仅依赖于前一行，则可以使用int mat[2][1000000];。计算出当前行后，可以立即丢弃前一行，切换当前和前一行。
2. 有时，可以使用std::map代替2D数组。
我在编程比赛中遇到过很多问题解决方案因具体情况而异，因此如果您提到a具体情况，我可能会给你一个更好的针对性的解决方案。

Answer 2

这在很大程度上取决于具体任务。没有万能的"诀窍"是永远有效的。你必须在特定的问题中寻找允许你用不同的方法解决它的东西。

也就是说，如果我真的没有其他办法，我会开始考虑这个矩阵中有多少元素真的是非零的(也许我可以使用稀疏数组或映射(字典)代替)。或者我不需要把所有的元素都存储在内存中，而是可以在每次需要的时候重新计算它们。

无论如何，一个那么大的矩阵(或者它的任何一种伪表示)是没有用的。不仅因为您没有足够的内存，还因为用数据填充这样的数组将花费几个小时到几个月的时间。这应该是您首先关心的问题——弄清楚如何用更少的数据和计算来解决任务。当您弄清楚这一点时，您还将看到合适的数据结构。