c - 如何压缩大小为1024*1024*1024*4的稀疏数组

Question

关闭。这个问题需要多问 focused 。目前不接受答案。

---

想要改进此问题吗？更新问题，使其仅关注一个问题 editing this post .

已关闭 6 年前。

Improve this question

我有一个稀疏数组，大小为 1024 * 1024 * 1024 * 4。该数组的项目是字节。所以数组的内存是4G。它是一个稀疏数组，即非零项只有600M左右。希望能够提出一种存储结构来压缩稀疏数组(压缩到2~3G)，并且具有良好的访问速度。

Answer 1

合适的表示取决于稀疏数组所需的操作。一般方法是将非零项的位置及其值存储在数据结构中。

一种选择是使用哈希表。

enum {NumDimensons = 4};
struct ArrayLocation {
  int16_t location[NumDimensions];
};

typedef uint8_t ArrayValue;

// Hash Table with key as ArrayLocation and value as ArrayValue

像 get() 和 put() 这样的哈希表操作很简单，但迭代却不是。如果迭代很重要，一种选择是使用二叉搜索树。