why does it run faster when it was converted from dense to sparse array?

user_489564 0
Viewed 103

To simplify, I have the test code below:

from scipy.sparse import csr_matrix, dok_array, issparse
import numpy as np
from tqdm import tqdm


X = np.load('dense.npy')
# convert it to csr sparse matrix
#X = csr_matrix(X)
print(repr(X))

n = X.shape[0]
with tqdm(total=n*(n-1)//2) as pbar:
    cooccur = dok_array((n, n), dtype='float32')
    for i in range(n):
        for j in range(i+1, n):
            u, v = X[i], X[j]
            if issparse(u):
                u = u.toarray()[0]
                v = v.toarray()[0]
                #import pdb; pdb.set_trace()
            m = u - v
            min_uv = u - np.maximum(m, 0)
            val = np.sum(min_uv - np.abs(m) * min_uv)
            pbar.update()

Case 1: Run as it is - the time usage is like this (2min 54sec): enter image description here

Case 2: uncomment the line X=csr_matrix(X) (just for the sake of comparison), the running time is 1min 56sec: enter image description here

It is so weird and I can't figure out why it is even slower to operate on dense array. I subsampled the array for this test; for the original array, the run time difference between sparse and dense array is big (due to the large number of iterations.)

I put the code into a function and used line_profiler to see the time usage. My findings are: 1. slice indeed is much slower for sparse matrix; 2. the 3 lines above last line are much faster in Case 2; 3. the total run time is smaller for Case 2 even it takes extra time for slicing and converting to dense vector.

I am so confused why these 3 lines costed different run time in Case 1 and Case 2 - they are exactly the same numpy vectors in the two cases. Any explanations?

The dense.npy file is uploaded to here to reproduce the observation.

scipy sparse-matrix python
1 Answers
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse import issparse

n = 1_000
sparsity = 0.98

A = np.random.rand(n, n)
A[A < sparsity] = 0
As = csr_matrix(A)

def _test(X):
    n = X.shape[0]
    for i in range(n):
        for j in range(i+1, n):
            u, v = X[i], X[j]
            if issparse(u):
                u = u.toarray()[0]
                v = v.toarray()[0]
            m = u - v
            min_uv = u - np.maximum(m, 0)
            val = np.sum(min_uv - np.abs(m) * min_uv)

Running this on dense:

%timeit _test(A)
5.3 s ± 21.4 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Running this on sparse:

%timeit _test(As)
1min 10s ± 1.06 s per loop (mean ± std. dev. of 7 runs, 1 loop each)

This makes sense as you're not actually using a sparse data structure for anything - you're just expensively and inefficiently converting it back to a dense data structure every time your inner loop iterates.

I don't know how you got the runtimes you got as the order of magnitude difference between dense and sparse is what I would expect for the code you have provided.

user_73409480
Related