最速の疎ベクトルはどれだ

海野です。
自然言語処理などで機械学習を行おうとすると、非常に疎なベクトル表現を使いたくなります。疎、というのはほとんどの要素が0である、という意味です。前々から疎ベクトルライブラリのパフォーマンスに関して気になっていたので、幾つか調べてみました。

Jubatus Workshopでも話したとおり、機械学習を適用しようとすると、普通は対象のデータをベクトル表現に落とします。特に言語データの場合は、それぞれの単語や文字などを特徴次元とするため、非常に疎なベクトルとなってしまいます。純粋な配列（C++で言えばstd::vector）を使ってしまうと、大量にメモリを食ってしまうため疎ベクトル専用の表現を使うのが普通です。

今日は様々な疎ベクトルライブラリのパフォーマンス比較を行おうと思います。比較したライブラリは以下のとおり。真の意味で、疎ベクトルのライブラリは、Eigenとublasだけで、残りは疎ベクトルの実装に使うためのライブラリという位置づけです。

std::vector<std::pair<uint32_t, float> >

標準ライブラリのvector表現。中身は、pair<uint32_t, float>で、インデックスと値のペアの配列で表現します。

unordered_map<uint32_t, float>

いわゆるハッシュマップ。インデックスから値へのマップで表現します。pficommonを利用。

Eigen

有名な高速ベクトルライブラリ。

boost ublas

これも有名なベクトルライブラリ。boostに依存してしまうのがネック。

dag_vector

岡野原さんの圧縮ベクトル。これ自体はintしか格納できないので、インデックスをdag_vectorに、値はstd::vectorに格納します。

さて、早速結果です。実験対象としては、100万次元、密度10%のランダム生成した疎ベクトルと、同じくランダム生成した密ベクトルとの積を、1000回計算します。MBA上で実行しています。

実行結果から以下のことが伺えます。

• 最速は単純なstd::vector
• ハッシュにすると2倍以上時間がかかる
• Eigenは最速にほとんど迫る速度
• ublasが想像以上に遅い。なぜか、dot関数だとstd::vectorより20倍以上遅く、単なるループのほうが速いがそれでも7倍近く遅い
• 追記: ublasは#define NDEBUGを付けないと遅いが、つけるとなかなか速くなる。それでもvectorやEigenには少し及ばない。それから、単なるfor-loopの方がやはり速い。上の表の取り消し済みは、NDEBUGなしのときのパフォーマンス。
• dag_vectorは流石にかなり遅い

おすすめは、Eigenでしょう。中身はおそらくstd::vector同等の実装になっていることが予想されます。実際は、templateでガリガリ書かれているので、中をちゃんと読むのは大変です。しかし、Eigen3 (3.0.3)の現状では、EIGEN_YES_I_KNOW_SPARSE_MODULE_IS_NOT_STABLE_YETを#defineしないと怒られてコンパイルできないという、ちょっとつらい状況。
また、Eigenもublasも、ベクトルのコンストラクタに次元数を渡さないと使えないというのが地味に辛い。自然言語処理のように、後から後から単語が追加されるのが普通の言語だと、最初に次元を指定しないとならないのは辛い。もちろん、計算のためにリサイズを毎回すればいいですが、あまり嬉しい状況ではないですね。
単純に疎ベクトルと密ベクトルの内積をとるくらいのことしかしないのであれば、実はstd::vectorが一番お勧めなんではないかという、お寒い結論になってしまいました。

追記：@thimura 様にご指摘を頂き、ublasで#define NDEBUGした追加実験しました。結果的に、ublasが致命的なほど遅いということはなかったようです。どうもありがとうございます。