STL風に使えるマップ型コンテナの紹介と性能比較

Tag

# ライブラリ

# 大規模データ処理

preferred

最近スマートフォンに乗り換えました。徳永です。

C++は世に数あるプログラミング言語の中では比較的メモリを食わない方ですが、それでもメモリ使用量が問題となる場合はあります。そのような場合の対処方法はいくつか有りますが、手軽に選択できる方法として、今日はSTLのmapやunordered_mapと同じ感じで使えるデータ構造をいくつか紹介したい思います。

以下、計算量の表記をする際には、要素数をnとします。

Loki::AssocVector

LokiはModern C++ Designという本の作者であるAndrei Alexandrescuが開発したライブラリです。AssocVectorはその中の一つとして提供されているクラスで、vector<pair<key, value> >という型のベクターをkeyでソートした状態で持つ事により、二分探索による要素の探索を可能にしたデータ構造です。これにより、探索はO(log(n))とmapと同じオーダーになり、かつメモリ使用量にはほとんどオーバーヘッドがない、という特徴を持ちます。よろしくない点としては、要素の挿入と削除がO(n)と遅いことが挙げられます。

なんと言っても、メモリ使用量の少なさがAssocVectorの魅力でしょう。今回紹介するすべてのデータ構造と比べて圧倒的にオーバーヘッドが少なく、速度面でもそれほど大きく劣りません。データの更新が発生しないのであれば、非常に魅力的なデータ構造です。

google-sparsehash

Googleからリリースされたハッシュテーブル系のライブラリです。内部ではsparsetableという配列を使っており、これは使用していない部分にはほとんどメモリを食わない配列になっています。sparsetableは要素を使っている/使っていないという情報をビットマップで管理しており、実際のキーと値の部分は使っている部分だけを密に詰め込んだ形になっています。簡潔データ構造脳の人がビットマップを見ると「rankを使ってアクセス位置を決めるんだろうな」と思うかもしれませんが、sparsetableでは小さな配列（デフォルトだと48要素単位で、この配列のことをグループと呼ぶそうです）をつなぎあわせて大きな配列を実現しています。グループを小さくすればするほど速度は向上しますが、オーバーヘッドは大きくなります。

sparsetableの一つ一つのグループのイメージを図示したのが下の図です。上の四角が要素の有無を表すビットマップを、下の四角が実際にキーと値が保存されているベクターを表現しています。例えば、三つ目の要素にアクセスすることを考えると、三つ目の位置から左側には（３つ目を含んで）二つの1があるので、下のベクターでは二つ目の要素にアクセスすることになります。

sparsehash自体は、sparsetableを使う以外には特に変わったところのない普通のハッシュテーブルです。衝突時の要素の解決は平方探査法が使われており、これもリニアチェイン法と比べてメモリ使用量を削減できている要因です。平方探査法はテーブル中の空き要素を多めに取らないと性能の劣化が激しくなる場合がありますが、sparsetableだと空き要素にかかるメモリオーバーヘッドは非常に少ない（グループ一つに対してオーバーヘッドはビットマップ48bit+その配列のアドレスサイズだけなので、一要素あたりに直すと約2bit）ので、割と大胆に空き要素を確保することができます。
探索はハッシュテーブルなので理想的な場合にはO(1)で、挿入と削除はO(M)です。AssocVectorと比べるとやはりオーバーヘッドは無視できないぐらいのサイズではありますが、非常に小さなオーバーヘッドで速度を大きく向上させている、バランスのよいデータ構造であると言えるでしょう。

STX B+ Tree

STX B+ TreeはTimo BingmannによるB+木の実装で、STLのmapとほぼ互換性があります。B+木なので、赤黒木で実装されることの多いSTLのmapと比べると、メモリ使用量の点で優れています。残念ながら、今回紹介する3つのデータ構造の中では一番メモリ使用量は大きいですが、ソート済みで範囲選択が可能であり、要素の挿入と削除もそこそこの時間(O(log(n)))でこなせるというメリットがあります。要素のキーと値がメモリ上で分離して配置されているせいでイテレータに対する書き込みが意味を持たないという問題点がありますが、ここら辺はSTLの仕様との兼ね合いなので、如何ともしがたいところです。

std::map

大体赤黒木で実装されているようです。別に赤黒木で実装しなければC++闇の軍団に襲われるということもないと思うのですが、私は仕様書までは読んでないのでそこら辺はよくわかりません。

std::unordered_map

C++0x以外の環境であれば、std::tr1::unordered_mapになります。大体ハッシュテーブルで実装されているようです。

実験

今回の実験では、メモリ使用量がどれぐらい変化するかに興味があります。純粋にコンテナのオーバーヘッドを見るため、キーと値の両方にintを使いました。メモリ使用量は/proc/processid/statusで計測しました。それぞれのコンテナで1000万要素を保持した場合のメモリ使用量を比較しています。コンパイラはg++の4.4.5を用い、最適化オプションは-O2でコンパイルしました。

メモリ使用量の比較

結果からわかる通り、AssocVectorの省メモリ性は圧倒的です。データの更新がないのであればAssocVector一択と言ってもいいぐらい、非常にメモリ使用量が少ないことがわかります。以下、google-sparsehash、STX B+ Tree、std::unordered_map、std::mapの順でメモリ使用量が増えました。unordered_mapとmapはもっと差がつくかと思いましたが、それほどメモリ消費量は変わりませんでした。

おまけで、速度も一応計測してみました。更新を行うとAssocVectorの速度が悲惨なことになるので参照だけですが、100万回の探索を行った結果です。グラフを作るのに疲れたので、表で済ませます。0,1,2… の順でシーケンシャルに探索しただけなので、ランダムにアクセスすると、データ構造によっては性能が変わるかもしれませんので注意してください。メモリ消費量がスケールが広すぎてグラフだと見難かったので、そちらも合わせて表に載せました。

	AssocVector	sprasehash	STX B+ Tree	map	unordered_map
メモリ消費量 (MB)	793.1	869.3	1935.6	4699.3	3929.5
構築時間 (秒)	2.42	6.33	9.60	17.4	5.26
探索時間 (秒)	0.50	0.25	0.82	7.36	0.09

まとめ

状況によって選択すべきデータ構造は変わりますが、データの更新が少なく、かつO(log(n))のアクセス速度で十分であれば、AssocVectorが良いでしょう。範囲選択も可能です。AssocVectorが不適で、かつ範囲選択が不要であればgoogle-sparsehashが望ましいと思われます。メモリ消費量も少なく、アクセス速度もかなりのものです。AssocVectorが不適でかつ範囲選択が必要であれば、STX B+ Treeが良さそうです。

今回は、標準でない3つのデータ構造を含む5つのデータ構造について、簡単にパフォーマンスの計測を行いました。実際にコードを使うとなると、コードの安定性、メンテナンスの継続性なども気になるところですが、ここで紹介したデータ構造はdebianパッケージにもなっているぐらいなので、大きな問題はないと考えてよいでしょう。

昨今では大きなデータを扱う機会も増えてきています。標準で提供されるライブラリではメモリが足りない、どうしてもメモリ使用量を後30%削減しないとダメだ、というような場合にこのエントリを思い出すと、役に立つかもしれません。