稀疏数据的3D数组与稀疏矩阵的比较

Question

我正在制作一个简单的银河系模型，其中一个需要存储的内容是一个三维的质量密度网格。

问题是，如果我给银河系周围画一个长方形的框，大部分网格单元都是空的。这就意味着我需要存储很多没用的零。所以，直接用数组来存储显得很浪费：

galaxy = [[[0 for k in xrange(1601)] for j in xrange(1601)] for i in xrange(253)]
# then fill in i,j,k values that are non-zero

我尝试用字典来构建一个稀疏数组：

for x in range(1601):
    for y in range(1601):
        for z in range (253):
            galaxy[str(x) + "," + str(y) + "," + str(z)] = # whatever

但是，（除了看起来不太好）我用作键的字符串占用了比我节省的内存还要多。我遇到了OutOfMemoryError错误，因为（我计算过）仅仅是这些键就占用了好几GB的内存。

在某个时候，我想提高模型的分辨率，这意味着我需要一个更大的网格。有没有比使用三维浮点数组更有效的存储方式呢？

我还担心遍历所有单元格（或者只是遍历网格中非零单元格）所需的时间。这一点非常重要。

Answer 1

你可以试着把数据存储在SQL表里，然后根据需要只加载一部分数据。这虽然会花一些时间来加载这些部分，但能节省内存。至于内存中的表示方式，可以参考其他回答中提到的方法，比如使用字典等等。

Answer 2

试试用字典的方法，不过只存储那些值不为零的键值对。一个更好的键可以是一个包含 (x,y,z) 的元组。

Answer 3

快速计算一下：1601 * 1601 * 253 => 648489853 项目。测试表明，在32位机器上，每个条目大约占用24字节，而在64位机器上则是49字节，所以总共大约需要 15,563,756,472 字节（在64位系统上大约是30GB）。其中的10%是1.5GB（在64位系统上是3.0GB）。如果你有一台64位的电脑，内存也很大，我觉得用稀疏表示法应该没问题。

我建议：

1. 用元组作为键，而不是字符串，
2. 使用稀疏存储系统，不存储零值。

这里有一个可能的方案：

class SparseDict(dict):
  def __init__(self, default_value):
    dict.__init__(self)
    self._value = default_value
  def __getitem__(self, key):
    try:
      return dict.__getitem__(self, key)
    except KeyError:
      return self._value
  def __setitem__(self, key, val):
    # I'm sure this can go faster if I were smarter
    if val == self._value:
      if  key in self:
        del self[key]
    else:
      dict.__setitem__(self, key, val)

def test(galaxy):
  import sys
  print len(galaxy), sys.getsizeof(galaxy)

  # test is 1/10th size in each dimension,
  # so 1/1000th of the volume
  for x in range(160):
    for y in range(160):
      for z in range (25):
        import random
        # 90% of space is essentially a vacuum
        if random.random() < .1:
          galaxy[x,y,z] = 1502100
        else:
          galaxy[x,y,z] = 0

  print len(galaxy), sys.getsizeof(galaxy)

test(SparseDict(0))