稀疏D的三维阵列与稀疏矩阵

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

我试着用字典建立一个稀疏数组：

^{pr2}$

但是，（除了难看之外）我用来做键的字符串占用了比我节省的更多的内存。我得到了OutOfMemoryErrors，因为（我计算过）仅密钥就占用了几千兆字节的内存。在

在某个时候，我想提高模型的分辨率，这意味着网格要大得多。有没有比使用3D浮点数组更有效地存储我的值的方法？

我还担心迭代所有单元格（或者只是网格中的非零单元格）所需的时间。这将是非常重要的。在

Answer 1

尝试使用字典方法，但只存储键：值对对于值为非零的键。更好的键可能是（x，y，z）的元组。在

Answer 2

也许可以尝试将数据保存在sql表中，并根据需要只加载多维数据集的一个子集。这将花费您加载部件的时间，但将节省您的内存。至于记忆中的表征，可以使用其他答案中建议的方法，如字典等。。。在

Answer 3

快速数学：1601 * 1601 * 253 => 648489853 items。一个测试表明，在32位机器上，字典每个条目占用24个字节，在64位机器上每个条目占用49个字节，因此 15563756472字节（或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))