Почему формат CSR превосходит формат CSC при выборе строк? - PullRequest
Новая
       10

Почему формат CSR превосходит формат CSC при выборе строк?

2 голосов
/ 28 апреля 2019

Я выполняю этот небольшой эксперимент по формату CSR и CSC на основе scipy.sparse.Как утверждает документация , формат CSC более эффективен, чем формат CSR, при работе с операциями со столбцами.Итак, я провел небольшой эксперимент: 

from scipy.sparse import diags
d = diags([-1, 1, 1], [-1, 0, -1], shape= (100, 100))
%timeit d.tocsc()[:, 1]
%timeit d.tocsr()[:, 1]

Тогда я полагаю, что неправильно понял строку и столбец.Поэтому я попробовал наоборот: 

%timeit d.tocsc()[1]
%timeit d.tocsr()[1]

Но в случаях CSR превосходит CSC по времени.Мне было интересно, есть ли какие-либо структурные причины для таких результатов, или мои тесты просто предвзяты?

1 Ответ

1 голос
/ 28 апреля 2019

Индексирование разреженных матриц является сложным, с рядом переменных, которые могут влиять на время. Ваш тестовый пример является симметричным, поэтому форматы csr и csc будут практически одинаковыми. Вещи могут отличаться, если форма прямоугольная или макет другой.

Кроме того, индексирование со скаляром по сравнению со срезом по сравнению со списком может отличаться.

Имейте в виду, что разреженная индексация, независимо от формата, намного медленнее, чем numpy.ndarray. Старайтесь не использовать разреженный, если вам нужно повторить. (И если вам нужно выполнить итерацию, рассмотрите возможность непосредственной работы с «необработанными» разреженными атрибутами.) 

In [64]: d = sparse.diags([-1, 1, 1], [-1, 0, 1], shape= (100, 100))                 
In [65]: d                                                                           
Out[65]: 
<100x100 sparse matrix of type '<class 'numpy.float64'>'
    with 298 stored elements (3 diagonals) in DIAgonal format>

In [66]: %timeit d.tocsr()[:,1]                                                      
422 µs ± 13.5 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
In [67]: %timeit d.tocsc()[:,1]                                                      
506 µs ± 5.89 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
In [68]: %timeit d.tocsc()[1,:]                                                      
506 µs ± 1.15 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

Отделить преобразование от индексации: 

In [69]: %%timeit x=d.tocsr() 
    ...: x[:,1]                                                                              
121 µs ± 2.05 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

In [70]: %%timeit x=d.tocsr() 
    ...: x[1,:]                                                                           
118 µs ± 2.95 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

In [71]: %%timeit x=d.tocsc() 
    ...: x[:,1]                                                                            
290 µs ± 5.89 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

In [72]: %%timeit x=d.tocsc() 
    ...: x[1,:]                                                                            
297 µs ± 14.2 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

Я немного удивлен, что csr время постоянно быстрее. Но только немного. csc и csr используют общий базовый класс compressed (sparse.compressed._cs_matrix), но детали кодирования, кажется, предпочтительнее csr.

===

И просто для удовольствия, индексируйте lil формат 

In [73]: %%timeit x=d.tolil() 
    ...: x[1,:]                                                                            
76.4 µs ± 231 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

In [74]: %%timeit x=d.tolil() 
    ...: x[:,1]                                                                       
118 µs ± 647 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

Как и ожидалось от хранилища lil, индексирование строк выполняется быстрее, хотя время индексации столбцов неплохое.

lil имеет getrow, который ближе всего в sparse к numpy представлению: 

In [75]: %%timeit x=d.tolil() 
    ...: x.getrow(1)                                                                          
36.7 µs ± 233 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

===

Плотная индексация массива, даже если время преобразования быстрее: 

In [83]: %%timeit x=d.A 
    ...: x[:,1]                                                                          
277 ns ± 9.97 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
In [84]: timeit d.A[:,1]                                                             
197 µs ± 587 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
...