Почему формат CSR превосходит формат CSC при выборе строк?
Я провожу этот небольшой эксперимент с форматом 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
Индексация разреженных матриц сложна из-за ряда переменных, которые могут повлиять на время. Ваш тестовый пример симметричен, поэтому форматы csr и csc будут почти одинаковыми. Все могло бы быть по-другому, если бы форма была прямоугольной или макет был другим.
Также индексация со скаляром, срезом и списком может отличаться.
Имейте в виду, что разреженное индексирование, независимо от формата, намного медленнее, чем numpy.ndarray. Старайтесь не использовать sparse, если вам нужно повторить. (И если вам необходимо выполнить итерацию, рассмотрите возможность работы непосредственно с «сырыми» разреженными атрибутами.)
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)
Спасибо, действительно познавательно!! Два дополнительных вопроса: каким-то образом, когда я тестировал на своем ноутбуке,
tolilбыл самым медленным из трех? и поэтому, если бы моя задача состояла в том, чтобы обрабатывать огромную диагональную полосатую матрицу в длинном цикле, должен ли я жертвовать своей памятью ради эффективности? (по вашему мнению)