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

问题描述

在scipy中，我们可以使用scipy.sparse.lil_matrix()等构造稀疏矩阵.但是该矩阵在2d中.

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?

p.s.我在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!

编辑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.

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