algorithm - 存储巨大的矩阵

Question

我有N x N字节矩阵N = 200,000,000。我想及时获得价值M[i, j]，O(1)并比内存更有效地将矩阵存储在硬盘上O(N*N)。矩阵不是稀疏的，但值始终在 0..255 之间。是不是没有希望了？

Answer 1

如果矩阵值是随机的 - 那么是的，你搞砸了。你需要一个 200MB^2 的磁盘。

如果矩阵有一个模式，那么它可能会存储它。这在很大程度上取决于您对矩阵的了解，以及是否可以对其进行安全转换。

我会有一个问题 - 矩阵中是否存在值无关紧要的区域？如果是这样，我会将它们归零而不是存储它们。