疎な配列(Sparse Array)

あんまりこれについて書かれてる記事がなかったので書いてみる。
(MathematicaにマニュアルがGoogleでトップにヒットするんだもん)

事の発端
RE2のソースを読んでて、SparseArrayなる入れ物があるのを発見。Sparse Arrayとは何ぞやと思い調べてみた。

分かったこと
タイトル通り、訳としては「疎な配列」。意味は配列自体は巨大なんだけど中身はすっからかんな配列。(実装が腐ってるとそうなる)
ハッシュマップと何が違うの？もともとは行列を扱うのに適したものだったらしい。なのですべての要素に初期値がある。(ハッシュマップにはない)
後、検索、挿入、削除などのアクセスが定数時間(O(1)ってこと？)。イテレーションにかかる時間がO(n)でnは要素数、配列のサイズではない。
普通の配列を使うより高速かつハッシュマップと違ってリサイズの心配がない。(動的な配列ではないた。、実装によると思うが)


何がハッシュマップに比べてよさげか
あくまで配列なので、ハッシュの計算をする必要がない。(RE2のSparseArrayはそうなってる)
RE2の実装ではイテレータはインデックスと値のpairを返す。(多分そうやってO(n)のイテレーションを実現してるのだろう、for(int i = 0; i < size; i++)とは書けないということだね)
リハッシュの心配がないので、メモリの見積もりが聞く。


何が単なる配列よりよさげか
総アクセス時間が要素数に対しての線形になる。(配列のサイズじゃない)

自前で実装するほどのメリットが今のところ見当たらない。結局メモリの節約になるわけでもないし。
あ、まてよ、RE1もRE2もコンパイルされた正規表現のインストラクションの数だけ配列つくってるなぁ。10000以上になってきたらさすがに総アクセス時間がパフォーマンスに影響を与えそうだ。
とりあえず、配列アクセス用のマクロ書いて、パフォーマンスチューニングの段階になったら考えるか。(こういうときC++だとtemplateが使えると便利だよなぁ・・・)