当大多数第二维空是空的时，什么是可存储空间最多的内存向量？

Question

我有一个大型的固定大小的可变大小的u32数组。大多数第二维数组都是空的（即第一个数组将被稀疏地填充）。我认为Vec是两种尺寸最合适的类型（Vec<Vec<u32>>）。因为我的第一个数组可能非常大，我想找到最节省空间的方式来表示这个。

我看到两个选择：

1. 我可以使用Vec<Option<Vec<u32>>>。我猜测，因为Option是一个标记的联合，这将导致每个单元格被sizeof(Vec<u32>)四舍五入到标签的下一个单词边界。
2. 我可以直接使用Vec::with_capacity(0)所有细胞。空Vec在使用之前是否分配零堆？

哪种节省空间的方法最多？

Answer 1

实际上，Vec<Vec<T>>和Vec<Option<Vec<T>>>都具有相同的空间效率。

A Vec contains a pointer that will never be null，所以编译器足够聪明，可以识别在Option<Vec<T>>的情况下，它可以通过在指针字段中输入0来表示None。 What is the overhead of Rust's Option type?包含更多信息。

指针指向的后备存储怎么样？ A Vec doesn't allocate（与第一个链接相同）当你用Vec::new或Vec::with_capacity(0)创建它时;在这种情况下，它使用一个特殊的非空“空指针”。 Vec只在你用push的东西或者强迫它分配时在堆上分配空间。因此，用于Vec本身和其后备存储的空间是相同的。

Answer 2

Vec<Vec<T>>是一个不错的起点。每个条目花费3个指针，即使它是空的，对于填充条目，可能会有额外的每个分配开销。但是，根据您愿意做出的权衡取舍，可能会有更好的解决方案。

• Vec<Box<[T]>>这将条目的大小从3个指针减少到2个指针。缺点是改变盒子中的元素数量既不方便（转换为Vec<T>）又更昂贵（重新分配）。
• HashMap<usize, Vec<T>>如果外部集合足够稀疏，这可以节省大量内存。缺点是更高的访问成本（散列，扫描）和更高的每元素内存开销。
• 如果集合仅填充一次并且您从未调整内部集合的大小，则可以使用拆分数据结构： 这不仅将每个条目的大小减少到1个指针，而且还消除了每个分配的开销。

  struct Nested<T> {
     data: Vec<T>,
     indices: Vec<usize>,// points after the last element of the i-th slice
  }
  
  impl<T> Nested<T> {
      fn get_range(&self, i: usize) -> std::ops::Range<usize> {
         assert!(i < self.indices.len());
         if i > 0 {
             self.indices[i-1]..self.indices[i]
          } else {
             0..self.indices[i]
          }
      }
  
      pub fn get(&self, i:usize) -> &[T] {
          let range = self.get_range(i);
          &self.data[range]
      }
  
      pub fn get_mut(&mut self, i:usize) -> &mut [T] {
          let range = self.get_range(i);
          &mut self.data[range]
      }
  }

  为了节省更多内存，您可以将指数减少到u32，每个集合限制为40亿个元素。