왜 파이썬에서 희소 매트릭스 컴퓨팅이 너무 느림

Question

내가 사용한 형식은 csr 스파 스 매트릭스이며, add 및 dot opertor에 대한 가장 빠른 스파 스 구조로 권장됩니다. 나는 그것의 성능을 np.array의 add와 dot 연산자와 비교했다. 그러나 스파 스 매트릭스에 대한 컴퓨팅이 밀도가 높은 형식의 경우보다 훨씬 느립니다. 왜 그럴까요? 스파 스 컴퓨팅을 구현하는 효율적인 방법이 있습니까?

import numpy as np 
import scipy.sparse as sp 
import random 

#%% generate dense vector 
vector_length = 10000 
nonzero_term = 200 

x = np.zeros((vector_length,)) 
y = np.zeros((vector_length,)) 

index = random.sample(range(vector_length), nonzero_term) 
x[index] = np.random.rand(nonzero_term) 
index = random.sample(range(vector_length), nonzero_term) 
y[index] = np.random.rand(nonzero_term) 

#%% transform to sparse vector 
x_sp = sp.csr_matrix(x) 
y_sp = sp.csr_matrix(y) 

#%% test 

# dense add 
%timeit [x + y] 
# sparse add 
%timeit [x_sp + y_sp]  
# dense dot 
%timeit [x.dot(y)] 
# sparse dot 
%timeit [x_sp.dot(y_sp.T)] 

및 결과가 조작

100000 loops, best of 3: 6.06 µs per loop 
10000 loops, best of 3: 97.8 µs per loop 
100000 loops, best of 3: 3.45 µs per loop 
1000 loops, best of 3: 225 µs per loop 

Answer 1

세트를 모두 나타낸다는 컴파일 된 코드를 사용합니다. 그러나 데이터는 상당히 다르게 저장됩니다.

x.shape은 (10000,); y도 마찬가지입니다. x+y 그냥 같은 모양의 배열을 할당하고 효율적으로 c 3 데이터 버퍼를 통해 단계.

x_sp은 0이 아닌 값이 200이고 값은 x_sp.data이고 열의 인덱스는 x_sp.indices입니다. 세 번째 배열 인 x_sp.indptr이 있지만 값은 2 개뿐입니다. y_sp에 대해서도 마찬가지입니다. 그러나 그것들을 추가하기 위해서는 4 개의 배열을 밟아야하고 두 개의 배열에 값을 할당해야합니다. c으로 코딩 된 경우에도 훨씬 더 많은 작업이 있습니다. 내 테스트의 경우 x_sp+y_sp에는 397 개의 0이 아닌 값이 있습니다.

이러한 1 차원 배열 (1 행 행렬)에서 dot은 동일한 종류의 스테핑 스루 (stepping through) 값을 포함하며 모든 값을 하나의 최종 값으로 합산합니다.

매트릭스의 밀도가 충분히 낮 으면 스파 스 계산이 더 빠를 수 있습니다. 이것은 행렬 곱셈이 더하기보다 사실이라고 생각합니다.

요약하면, 요소 당 계산은 희소 행렬을 사용하면 더 복잡합니다. 따라서 요소가 거의 없더라도 전체 시간은 길어지는 경향이 있습니다.