AndroidのSparseArrayは本当に速いのか測定してみた

前回のエントリで紹介したBundleSaverを作成する際に、SparseArrayというクラスの存在を知りました。

SparseArrayは、Android向けにつくられたパフォーマンスに優れたHashMap代用とのことで、その使い方と気になる性能について調べてみました。
実際に測定することでメリットやデメリットがわかったので、ご紹介します。

1. SparseArrayってなぁに？
2. どう使うの？
3. HashMap と SparseArray の性能比較
4. 考察
5. まとめ
6. 参考（計測に利用したクラス）

　 1. SparseArrayってなぁに？

SparseArrayは、キーにintを利用することを前提としたHashMapだと考えると分かりやすいかと思います。
（Integerではなく、intです。）

また、SparseArrayでは、値にObject型を格納できますが、値がint, booleanの場合は、それぞれSparseBooleanArray, SparseIntArrayというクラスも用意されています。

内部にはキー用の配列、値用の配列を個別に持ち、配列添字による取得以外は、基本的に二分木探索で目的の値を取得するつくりになっています。
また、保持するキーと値のペアを削除する際は、内部的に削除フラグを立て、随時寄せる処理を行っていました。
おそらく配列を有効利用することで不要なメモリ消費を押さえる目的と思われます。

　 2. どう使うの？

基本的にはHashMapと同様です。

SparseArray.keyAt(int index)で、キー配列の添字に該当するキーを取得します。
SparseArray.valueAt(int index)で、値配列の添字に該当するキーを取得します。
もちろん、キーが分かっているので、SparseArray.get(int key)でも構いません。

　 3. HashMap と SparseArray の性能比較

SparseArrayは、Androidの静的解析ツールLintでも対応すべき対策として指摘されるとのことなので、効率的なのだろうとは思いますが、実際にどういう面で効率的なのかが分からなかったので、性能調査を行いました。

調査環境

• Android Emulator
• Android 2.3.3

調査方法

• onCreate時に、HashMapとSparseArrayを生成し、任意の数のキー、値のペアを操作する。
• 操作内容は、put, getとし、対象の全キー操作完了までの時間を計測する。
• なお、キー一覧の生成時間は計測時間から除外する。

計測結果
　計測結果は以下のとおり

Put操作

Get操作

Put/Get操作の合計

　 4. 考察


上記結果から、処理対象が増加するほどSparseArrayのほうがパフォーマンスが出ると見なすことができます。

興味深いのは、処理時間の内訳です。
ご覧のとおり、put処理では、HashMapがかなり時間がかかっているにも関わらず、get処理では、HashMapのほうが処理速度は速くなっています。

これはそれぞれが採用するアルゴリズムの違いが差として現れていると考えられます。
HashMapが採用するアルゴリズムはハッシュ探索なので、値格納時にハッシュ関数処理とハッシュ表の作成処理が必要です。
その代わり、探索はハッシュ関数による格納位置を求めるだけですみます。
これがputが遅く、getが速い理由です。

一方、SparseArrayは探索アルゴリズムに二分探索木を採用しています。
これは、値格納時にキーの大小比較を行う程度で済みますが、探索は二分探索木で行われるため、線形探索に比べれば圧倒的に速いとはいえ、
件数が多くなるほど時間がかかるようになってしまいます。

メモリの観点から

メモリ利用率からも測定を行いました。
（とはいえ、GC発生回数という簡易な測定です…。目安にはなるかと思います。）

GC発生回数

HashMapのほうがGC発生頻度が高く、SparseArrayがメモリを効率的に利用していることがわかります。

　 5. まとめ 

まとめです。

• 速度面、負荷面の観点で、SparseArrayはHashMapより高いパフォーマンスを発揮する。
• ただし、Put後のGet処理が多く、性能が求められる用途（キャッシュなど）ではHashMapの利用を検討してもよい。
• その際はソフトリファレンス等を効果的に使い、メモリ圧迫を回避する手段を講じること。

　 6. 参考（計測に利用したクラス）

性能測定で利用したクラスです。
これらのTaskを別途準備した計測用のクラスに渡して計測を行いました。

こういう計測を行ったほうが効果的だよというのがあればご指摘もらえればと思います。


-------------------
以上です。HashMapとSparseArrayの使い分けに関して、何かの参考になれば幸いです。
ではでは。