Androidアプリのパフォーマンス 改善①（Map、Set）

この記事では、Androidアプリのパフォーマンス改善のための、方法について記載しています。

改善対象

MapやSetを特定の条件で絞りたい場合、filter関数を使うことがあると思います。
https://kotlinlang.org/api/latest/jvm/stdlib/kotlin.collections/filter.html

filterはとても便利な関数ですが、パフォーマンスとしては注意が必要です。

計測

1から１００までのキーを持つMapから、キーが９１以上のマップをfilterする場合、JUnitで処理時間を計測したところ、１００００回の平均値で、26,731nsでした。

    companion object {
        private const val MAP_SIZE = 100L
        private const val NUMBER_OF_MEASUREMENT = 10000
    }

    @Test
    fun mapTest() {
        val map = mutableMapOf<Long, String>()
        for (i in 1..MAP_SIZE) {
            map[i] = i.toString()
        }
        measurementTime {map.filter { it.key > map.size - 10 }}
    }

    private fun measurementTime(task: () -> Unit) {
        var sum = 0L
        for (i in 1..NUMBER_OF_MEASUREMENT) {
            val startTime = System.nanoTime()
            task()
            sum += System.nanoTime() - startTime
        }
        println("average=${sum / NUMBER_OF_MEASUREMENT}")
    }

filter関数は、指定された条件をMapの先頭から検索していくため、要素数が増えると検索する時間も増えます。
上記のMapのサイズを1000にして、条件も９９１以上とすると、39,850nsとなります。
（ワーストケースを考えて、あえて時間がかかるような検索条件にしています）

改善方法

これを改善する方法の一つとして、TreeMapがあります。
上記のテストを下記のように変更することで、処理時間はMapサイズが100の場合は840ns、Mapサイズが1000の場合は829nsとなりました。

    fun mapTest() {
        val treeMap = TreeMap<Long, String>()
        for (i in 1..MAP_SIZE) {
            treeMap[i] = i.toString()
        }
        measurementTime {treeMap.tailMap(treeMap.size - 10L, false)}
    }

これは、TreeMapは内部で、２分探索を行っており、Mapのサイズが大きくなっても、検索時間に影響が出にくいためです。

TreeMapにはsubmapがあり、filterと同様に範囲指定も行えます。
https://developer.android.com/reference/kotlin/java/util/TreeMap#submap

Setの場合は、TreeSetがあり、同様の処理（tailSet、subSet）が行えます。
https://developer.android.com/reference/java/util/TreeSet