Python 中的稀疏 3d 矩阵/数组? [英] sparse 3d matrix/array in Python?

问题描述

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

In scipy, we can construct a sparse matrix using scipy.sparse.lil_matrix() etc. But the matrix is in 2d.

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

I am wondering if there is an existing data structure for sparse 3d matrix / array (tensor) in Python?

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

p.s. I have lots of sparse data in 3d and need a tensor to store / perform multiplication. Any suggestions to implement such a tensor if there's no existing data structure?

推荐答案

很高兴提出一个(可能很明显的)实现，如果你有时间和空间来做新的，可以用纯 Python 或 C/Cython 实现依赖项，并且需要它更快.

Happy to suggest a (possibly obvious) implementation of this, which could be made in pure Python or C/Cython if you've got time and space for new dependencies, and need it to be faster.

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

A sparse matrix in N dimensions can assume most elements are empty, so we use a dictionary keyed on tuples:

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))

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

You could make this implementation more robust by verifying that the input is in fact a tuple, and that it contains only integers, but that will just slow things down so I wouldn't worry unless you're releasing your code to the world later.

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

EDIT - a Cython implementation of the matrix multiplication problem, assuming other tensor is an N Dimensional NumPy array (numpy.ndarray) might look like this:

#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

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

Although you will always need to hand roll this for the problem at hand, because (as mentioned in code comment) you'll need to define which indices you're summing over, and be careful about the array lengths or things won't work!

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

EDIT 2 - if the other matrix is also sparse, then you don't need to do the three way looping:

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 实现的建议是使用一个简单的结构来保存索引和值:

My suggestion for a C implementation would be to use a simple struct to hold the indices and the values:

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

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

you'll then need some functions to allocate and maintain a dynamic array of such structs, and search them as fast as you need; but you should test the Python implementation in place for performance before worrying about that stuff.

这篇关于Python 中的稀疏 3d 矩阵/数组?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！