python - Python中的稀疏3d矩阵/数组？

Question

在 scipy 中，我们可以使用 scipy.sparse.lil_matrix() 等构造一个稀疏矩阵。但是矩阵是二维的。

我想知道 Python 中是否存在用于稀疏 3d 矩阵/数组(张量)的数据结构？

附言我在 3d 中有很多稀疏数据，需要一个张量来存储/执行乘法。如果没有现有的数据结构，有什么建议可以实现这样的张量？

Answer 1

很高兴提出一个(可能是显而易见的)实现，如果您有时间和空间来构建新的依赖项，并且需要它更快，则可以使用纯 Python 或 C/Cython 实现。

N 维的稀疏矩阵可以假设大多数元素为空，因此我们使用以元组为键的字典:

class NDSparseMatrix:
  def __init__(self):
    self.elements = {}

  def addValue(self, tuple, value):
    self.elements[tuple] = value

  def readValue(self, tuple):
    try:
      value = self.elements[tuple]
    except KeyError:
      # could also be 0.0 if using floats...
      value = 0
    return value

你会像这样使用它:

sparse = NDSparseMatrix()
sparse.addValue((1,2,3), 15.7)
should_be_zero = sparse.readValue((1,5,13))

您可以通过验证输入实际上是一个元组并且它只包含整数来使这个实现更加健壮，但这只会减慢速度，所以除非您将代码发布到以后的世界。

EDIT - 矩阵乘法问题的 Cython 实现，假设其他张量是 N 维 NumPy 数组 (numpy.ndarray) 可能如下所示:

#cython: boundscheck=False
#cython: wraparound=False

cimport numpy as np

def sparse_mult(object sparse, np.ndarray[double, ndim=3] u):
  cdef unsigned int i, j, k

  out = np.ndarray(shape=(u.shape[0],u.shape[1],u.shape[2]), dtype=double)

  for i in xrange(1,u.shape[0]-1):
    for j in xrange(1, u.shape[1]-1):
      for k in xrange(1, u.shape[2]-1):
        # note, here you must define your own rank-3 multiplication rule, which
        # is, in general, nontrivial, especially if LxMxN tensor...

        # loop over a dummy variable (or two) and perform some summation:
        out[i,j,k] = u[i,j,k] * sparse((i,j,k))

  return out

尽管您总是需要针对手头的问题手动滚动，因为(如代码注释中所述)您需要定义要求和的索引，并注意数组长度或获胜的东西不行!

EDIT 2 - 如果另一个矩阵也是稀疏的，那么你不需要做三路循环:

def sparse_mult(sparse, other_sparse):

  out = NDSparseMatrix()

  for key, value in sparse.elements.items():
    i, j, k = key
    # note, here you must define your own rank-3 multiplication rule, which
    # is, in general, nontrivial, especially if LxMxN tensor...

    # loop over a dummy variable (or two) and perform some summation 
    # (example indices shown):
    out.addValue(key) = out.readValue(key) + 
      other_sparse.readValue((i,j,k+1)) * sparse((i-3,j,k))

  return out

我对 C 实现的建议是使用一个简单的结构来保存索引和值:

typedef struct {
  int index[3];
  float value;
} entry_t;

然后，您将需要一些函数来分配和维护此类结构的动态数组，并尽可能快地搜索它们；但是你应该在担心这些东西之前测试 Python 实现的性能。