2014年12月3日0件のコメント前回の記事で予告した記事が遅くなってしまった。ここでは、Pythonの疎行列ライブラリscipy.sparseについて、データの内部構造を説明する。内部構造を知らずにブラックボックスとして使いたい場合は前回の記事を参照のこと。はじめに(あるいは前回記事のまとめのまとめ)scipy.sparseで疎行列を表すクラスは主に以下のものがある(他にもあるが、ここではとりあげない。これだけ知ってれば大体のことはできる。)lil_matrixcsr_matrixcsc_matrix通常は、lil_matrixを用意してそこに値を詰めてから、csr_matrixまたはcsc_matrixに変換してから計算を行う。csr_matrixとcsc_matrixのどちらを使うかは以下のことから判断する。以下csr_matrixとcsc_matrixのデータ内部構造について説明する。このCSRとCSCという形式は、Pythonに限定された話ではなく、数値計算で疎行列を扱うときに一般的に使われるものである。...という風に0からナンバリングして呼ぶことにする。「i行目」「j列目」というときも、0を起点として考える。indptrで構成される。dataには行方向に非ゼロ要素の値が格納される。(dataのサイズは非ゼロ要素の数)indices[j]はdata[j]が何列目の要素かを示す。(indicesのサイズはdataのサイズに等しい)jがindptr[i]以上indptr[i+1]未満の範囲にあるときに、data[j]およびindices[j]はi行目の要素である。indptrはdataおよびindicesにおいて、どこからどこまでが同じ行かを示す。(indptrのサイズは行列の行数+1)実際の例を以下に示す。上図の行列で、行0、行1、行2にはそれぞれ、2個、1個、2個の非ゼロ要素がある。したがって、dataおよびindicesは両方とも2,1,2のサイズに区切り、それぞれの行の情報を格納する。indices[1]には1,2が格納される。行0の情報はdata[0]とindices[0]から始まるので、indptr[0]には0が入り、行1の情報はdata[2]とindices[2]から始まるので、indptr[1]には2が入る。以下同様に格納される。実際の実行セッションは以下のようになる。indptrで構成される。csrの説明で、「行」と「列」を入れ替えるとcsc_matrixの内部構造の説明になる。以下のようなことになる。dataには列方向に非ゼロ要素の値が格納される。(dataのサイズは非ゼロ要素の数)indices[j]はdata[j]が何行目の要素かを示す。(indicesのサイズはdataのサイズに等しい)jがindptr[i]以上indptr[i+1]未満の範囲にあるときに、data[j]およびindices[j]は列iの要素である。indptrはdataおよびindicesにおいて、どこからどこまでが同じ列かを示す。(indptrのサイズは行列の列数+1)具体例は図だけを示す。内部構造を知っていると何がうれしいか内部構造を理解することで、高速な操作ができるケースがある。非ゼロ要素に同一関数を作用させるケースについては以前のブログで書いたが、ここではコンストラクタの高速化の話をする。新しく、行列をつくるとき、(公式ドキュメントのユースケースにかかれているように)lil_matrixに詰めてからcsr_matrix(またはcsc_matrix)に変換するよりも、csr_matrix(またはcsc_matrix)の内部構造を直接用意してコンストラクトしたほうが処理速度が速い。実際に、次のような行列について、初期化にどのくらいかかるかのベンチマークを取ってみる。&2\end{pmatrix}\]ベンチマークに使ったコードは以下の通り。ここではサイズ10000×10000の行列で実験している。set_csr")そして、ある環境における実行結果が以下の通り。0.0562081336975csr_matrixに直接詰めたほうが圧倒的に速い。いえ、csr_matrixに直接詰めるコードの方が複雑になるので、開発効率の面からlil_matrixを利用する選択肢も捨てがたいかと思う。csr_matrix(またはcsc_matrix)に直接詰めるのが有効なのは以下のような場合かと考えられる。疎行列を何度も用意しなければいけない場合(一度用意するだけならあまりパフォーマンスの違いは気にならないかもしれない)データがあらかじめある程度ソートされた形で用意されている場合(オンラインアルゴリズムのような、次にどの非ゼロ要素がくるかわからないような状況だと、lil_matrixを使ったほうが手っ取り早いし、そこでわざわざソートするのならパフォーマンスの優位性は薄れる)まとめscipy.sparseを使うとき、通常はlil_matrixを用意して値を入れて、csr_matrixかcsc_matrixに変換してから計算する。そのように使っている限りは内部構造を知る必要はなく、ブラックボックスとして使える。場合によっては、csr_matrixやcsc_matrixに直接値を詰めたり、中身をいじったりするほうが、計算速度が速くなる。そのためには内部データ構造を理解する必要がある。csc_matrixの図が間違っていたので修正しました。指摘していただいた@KeWata09さんに感謝します。コメントをキャンセルメールアドレスが公開されることはありません。