파이썬에서 희소 3D 행렬 / 배열?

파이썬에서 희소 3D 행렬 / 배열?

---

scipy에서는 scipy.sparse.lil_matrix () 등을 사용하여 희소 행렬을 만들 수 있습니다. 그러나 행렬은 2d입니다.

Python에서 희소 3D 행렬 / 배열 (텐서)에 대한 기존 데이터 구조가 있는지 궁금합니다.

추신 3d에 많은 희소 데이터가 있으며 곱셈을 저장 / 수행하려면 텐서가 필요합니다. 기존 데이터 구조가없는 경우 이러한 텐서를 구현하기위한 제안이 있습니까?

---

새로운 종속성을위한 시간과 공간이 있고 더 빨라야하는 경우 순수 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))

입력이 실제로 튜플이고 정수만 포함되어 있는지 확인하여이 구현을 더 강력하게 만들 수 있지만 나중에 코드를 세상에 공개하지 않는 한 걱정하지 않을 것입니다.

편집 -행렬 곱셈 문제의 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

당면한 문제에 대해 항상 손으로 굴려야 할 필요가 있지만 (코드 주석에서 언급했듯이) 합산 할 인덱스를 정의해야하고 배열 길이에주의해야합니다. 그렇지 않으면 작동하지 않을 것입니다. !

편집 2- 다른 행렬도 희소 한 경우 3 방향 루핑을 수행 할 필요가 없습니다.

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 구현을 테스트해야합니다.

---

sparray-Python의 희소 n 차원 배열을 살펴보십시오 (Jan Erik Solem 작성). github 에서도 사용할 수 있습니다 .

---

올해의 대안은 sparse패키지입니다. 패키지 자체에 따르면 NumPy 위에 희소 다차원 배열을 구현 scipy.sparse하고 scipy.sparse.coo_matrix레이아웃 을 일반화합니다 .

다음은 문서에서 가져온 예입니다.

import numpy as np
n = 1000
ndims = 4
nnz = 1000000
coords = np.random.randint(0, n - 1, size=(ndims, nnz))
data = np.random.random(nnz)

import sparse
x = sparse.COO(coords, data, shape=((n,) * ndims))
x
# <COO: shape=(1000, 1000, 1000, 1000), dtype=float64, nnz=1000000>

x.nbytes
# 16000000

y = sparse.tensordot(x, x, axes=((3, 0), (1, 2)))

y
# <COO: shape=(1000, 1000, 1000, 1000), dtype=float64, nnz=1001588>

---

Nicer than writing everything new from scratch may be to use scipy's sparse module as far as possible. This may lead to (much) better performance. I had a somewhat similar problem, but I only had to access the data efficiently, not perform any operations on them. Furthermore, my data were only sparse in two out of three dimensions.

I have written a class that solves my problem and could (as far as I think) easily be extended to satisfiy the OP's needs. It may still hold some potential for improvement, though.

import scipy.sparse as sp
import numpy as np

class Sparse3D():
    """
    Class to store and access 3 dimensional sparse matrices efficiently
    """
    def __init__(self, *sparseMatrices):
        """
        Constructor
        Takes a stack of sparse 2D matrices with the same dimensions
        """
        self.data = sp.vstack(sparseMatrices, "dok")
        self.shape = (len(sparseMatrices), *sparseMatrices[0].shape)
        self._dim1_jump = np.arange(0, self.shape[1]*self.shape[0], self.shape[1])
        self._dim1 = np.arange(self.shape[0])
        self._dim2 = np.arange(self.shape[1])

    def __getitem__(self, pos):
        if not type(pos) == tuple:
            if not hasattr(pos, "__iter__") and not type(pos) == slice: 
                return self.data[self._dim1_jump[pos] + self._dim2]
            else:
                return Sparse3D(*(self[self._dim1[i]] for i in self._dim1[pos]))
        elif len(pos) > 3:
            raise IndexError("too many indices for array")
        else:
            if (not hasattr(pos[0], "__iter__") and not type(pos[0]) == slice or
                not hasattr(pos[1], "__iter__") and not type(pos[1]) == slice):
                if len(pos) == 2:
                    result = self.data[self._dim1_jump[pos[0]] + self._dim2[pos[1]]]
                else:
                    result = self.data[self._dim1_jump[pos[0]] + self._dim2[pos[1]], pos[2]].T
                    if hasattr(pos[2], "__iter__") or type(pos[2]) == slice:
                        result = result.T
                return result
            else:
                if len(pos) == 2:
                    return Sparse3D(*(self[i, self._dim2[pos[1]]] for i in self._dim1[pos[0]]))
                else:
                    if not hasattr(pos[2], "__iter__") and not type(pos[2]) == slice:
                        return sp.vstack([self[self._dim1[pos[0]], i, pos[2]]
                                          for i in self._dim2[pos[1]]]).T
                    else:
                        return Sparse3D(*(self[i, self._dim2[pos[1]], pos[2]] 
                                          for i in self._dim1[pos[0]]))

    def toarray(self):
        return np.array([self[i].toarray() for i in range(self.shape[0])])

참고URL : https://stackoverflow.com/questions/7685128/sparse-3d-matrix-array-in-python