前回の記事に続いて疎行列の話です。
参考:scipyにおける疎行列
今回は疎行列を実装する型(クラス)のうち、csc_matrixとcsr_matrixの紹介です。
前回紹介した、lil_matrixには効率的に疎行列を構成できるメリットがありますが、
計算が遅いというデメリットがあります。
ドキュメントに次のように書いてある通り、演算するときはcsrかcsc形式に変換した方が良いです。
arithmetic operations LIL + LIL are slow (consider CSR or CSC)
とりあえず本当に遅いのか時間を測っておきましょう。
今回は 10000*10000の大きめの疎行列を作り、実験します。
(arrayの場合の時間も測定したいので、最初にarrayで作成して変換していますが、本来は最初からlil型で生成してメモリを節約の恩恵を受けた方が良いです。)
また、csrと、cscはそれぞれ行方向、列方向の取り出しに有利という特徴があるので、実験用データによって有利不利無いように対称行列を作りました。
from scipy import sparse
import numpy as np
# 疎行列作成
M_array = np.random.choice(
[0, 1, 2, 3, 4, 5],
p=[0.99, 0.002, 0.002, 0.002, 0.002, 0.002],
size=[10000, 10000]
)
# 自身の転置行列と足し合わせて対称行列にする
M_array = M_array + M_array.T
# それぞれの型に変換する
M_lil = sparse.lil_matrix(M_array)
M_csc = sparse.csc_matrix(M_lil)
M_csr = sparse.csr_matrix(M_lil)
# 和をとるのにかかる時間を計測
%timeit M_array + M_array
# 406 ms ± 2.5 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
%timeit M_lil + M_lil
# 618 ms ± 7.04 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
%timeit M_csc + M_csc
# 7.92 ms ± 17.9 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
%timeit M_csr + M_csr
# 7.94 ms ± 51.8 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
ご覧の通り、 lil 同士の演算は通常のarray形式よりも遅く、一方でcscやcsr同士の演算は圧倒的に速くなりました。
あとは、cscとcsrの違いですが、それぞれ、列方向のスライスと行方向のスライスが効率的に行えます。
(あまり指摘されないようですが、スライスをとるだけであればarrayが一番早い。)
これもそれぞれみておきましょう。
# 列方向のスライス
%timeit M_array[:, 400]
# 225 ns ± 3.06 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
%timeit M_lil[:, 400]
# 11.4 ms ± 201 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
%timeit M_csc[:, 400]
# 151 µs ± 2.73 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
%timeit M_csr[:, 400]
# 2.86 ms ± 127 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
列方向のスライスについては、array が最速ではありますが、 csc が csr に比べてかなり早いことが確認できます。
次は行方向。
# 行方向のスライス
%timeit M_array[400, :]
# 235 ns ± 10.1 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
%timeit M_lil[400, :]
# 36.6 µs ± 1.37 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
%timeit M_csc[400, :]
# 2.9 ms ± 112 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
%timeit M_csr[400, :]
# 66 µs ± 3.39 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
今度は、csr が csc より速くなりました。
とはいえ、lil が csrよりも速く処理できています。(array最速は変わらず。)
これは、前回の記事で説明した通り、lilがrows属性に、行ごとの値を保有しているからのようです。
csrの方が演算が速く、わざわざ疎行列を作ったうえでなんの演算もせずにスライスで値を取り出すだけという場面もあまり無いので、
csrかcscを選んで使うことが多いと思いますが、行方向のスライスだけならlilが速いことは一応覚えておこうと思います。