疎行列のデータ構造入門再び

やあみんな。秋シーズンもいよいよ本番だね、今日なんかはもみじ狩りに最適なんじゃないかこれ。
以前疎行列のデータの持ち方について書いたけど読み返してみると本命のCCSやCRSの説明は最後までせずに回り道だけして終ってしまうという非常に残念な内容となっていたので反省もこめてちょっと書き直してみたよ。
みんなはCCSとかCRSとかって聞いたことあるかな。疎行列とは殆どの要素がゼロで、非ゼロ要素はわずかしかない行列のことだ。なので、だったらゼロでないもののみを覚えておけばいいじゃないかという発想だ。
簡単のため、５ｘ５の疎行列を考えよう（実際はもっと大きい要素数のケースが多いし、もっと疎なわけだが）

0.0, 2.0, 0.0, 0.0, 0.0
0.0, 0.0, 2.0, 0.0, 0.0
0.0, 1.0, 5.0, 2.0, 0.0
0.0, 3.0, 0.0, 0.0, 2.0
0.0, 0.0, 7.0, 0.0, 0.0

殆どの要素がゼロなので、各非ゼロ要素の、行idと列idと値とをセットにしたものを全て覚えておけば効率がよさそうだ。

// 行IDと列IDと、値を、セットにして覚える。
struct CompressedStorage
{ 
 int _i; 
 int _j; 
 float _val;
};
CompressedStorage cs[]={
  ( 0, 1, 2.0 ),
  ( 1, 2, 2.0 ),
  ( 2, 1, 1.0 ),
  ( 2, 2, 5.0 ),
  ( 2, 3, 2.0 ),
  ( 3, 1, 3.0 ),
  ( 3, 4, 2.0 ),
  ( 4, 2, 7.0 ) 
};

さあこれでよしと。だがちょっと待とう。まだ冗長なことに気づくはずだ。同じ行のエントリについては、その行IDを何度も記述する必要はないはずだよな。ある行についてのエントリはまとめて宣言するという決まりにして、あとは、その行の列IDと値とをセットで覚えておくだけでよいはずだ。つまり情報の並びとしては、

 ０行目 ( 1, 2.0 ),
 １行目 ( 2, 2.0 ),
 ２行目 ( 1, 1.0 ),  ( 2, 5.0 ),  ( 3, 2.0 ),
 ３行目 ( 1, 3.0 ), ( 4, 2.0 ),
 ４行目 ( 2, 7.0 )

で十分だろう。考え方としては「全非ゼロ要素を行idでソートして格納保存する」という考え方になる。
なのでこれを覚えておける構造体を考えよう。っていうだけの話だ。もうこの話は最後までそれだけの話しになるよ子供たちここまではいいかな？
さて、いろんな構造体の持ち方が考えられるけど、これを見てまさか行ごとに要素格納する配列をもつなんてのは効率が悪いよな。たった一つの配列の中に上記の上から順に全エントリをまとめて格納して、その中でi行目の先頭要素は何番目から始まり、i+1行目の先頭要素は何番目から始まります、という情報があればそれでよさそうだ。

 struct CompressedRowStorage
 {
   vector< int > _first_column_ids;
   vector< pair< int, float > > _entry_vec;
 };
 //
 //
 _first_column_ids の中身： { 0, 1, 2, 5, 7 }
 _entry_vec の中身：
 ( 1, 2.0 ),
 ( 2, 2.0 ),
 ( 1, 1.0 ),  
 ( 2, 5.0 ), 
 ( 3, 2.0 ),
 ( 1, 3.0 ),
 ( 4, 2.0 ),
 ( 2, 7.0 )

これが疎行列のCRS（Compressed Row Storage）表記というわけだ。Compressedは圧縮されたという意味だよ。
さて世の中には上から下にに並べた方がしっくりくる人もいるし、左から右に並べた方が便利な場合もあって、以上の話を、「全非ゼロ要素を列idでソートして格納保存する」というのを実践したのが、CCS（Compressed Column Storage）というわけだ。その構造体は以下のようになる。

 struct CompressedColumnStorage
 {
   vector< int > _first_row_ids;
   vector< pair< int, float > > _entry_vec;
 };

ていうかCRSと同じだね。一つ目の変数名が変わっただけだから、縦横の意味が入れ替わっただけで全く同じだ。
どれだけ行列が疎であるかによるわけだけれども、必要なメモリも数百分の１、数万分の１になるわけだ、なのでこの構造体を使ったアルゴリズムも数百倍とか数万倍とか高速なものが記述できるというわけさ。
でもあまり疎でない行列に対してこれをやってしまうと、行列まるごと配列として持つナイーブな表記法の場合よりも効率はぐっと下がってしまうので気をつけてくれ。
これを使ったアルゴリズムを考えるのはまたの機会にしよう。はい、今日はこんなとこで。