各種Mapへの要素追加、ランダムアクセス、イテレーションの実行速度

Kotlinで使用できるMapは主に

• HashMap (hashMapOf)
• LinkedHashMap (mutableMapOf）
• TreeMap (sortedMapOf)

の3つ。

結論から書くと、

• 要素の追加はHashMapが最も速い。次にLinkedHashMap。TreeMapは遅い。
• ランダムアクセスはHashMapとLinkedHashMapがほぼ同じ。TreeMapは遅い。
• イテレーションはLinkedHashMapが圧倒的に速い。

LinkedHashMapはキーの挿入順を保持しているのでイテレーションが高速に行える。

それぞれを使い分けるなら、

• ランダムアクセスのみ行う→HashMap
• イテレーションを行う→LinkedHashMap
• キーがソートされていると嬉しい→TreeMap

といった感じだろうか。

計測

 で各処理を行い、100回計測した平均を取る。

要素の追加（更新）

for(i in (1..N).map{Random.nextInt(N)}){
    map[i] = 1
}

HashMap	5.35 msec
LinkedHashMap	7.39 msec
TreeMap	34.63 msec

ランダムアクセス

事前に要素の追加と同じく要領でMapを埋めておく。

val keys = map.keys.shuffled()
for(i in keys){
    map[i]!!
}

HashMap	4.45 msec
LinkedHashMap	4.86 msec
TreeMap	30.54 msec

イテレーション

事前に要素の追加と同じく要領でMapを埋めておく。

for((k, v) in map){
    k + v
}

HashMap	3.97 msec
LinkedHashMap	0.93 msec
TreeMap	6.91 msec

コード全体

import kotlin.system.*
import kotlin.random.Random

val N = 100_000
val M = 100

val randomArray = Array(M){IntArray(N){Random.nextInt(N)}}
val randomPair = Array(M){randomArray[it].map{it to 1}}

fun main(){
    val maps = listOf(hashMapOf<Int, Int>(), linkedMapOf<Int, Int>(), sortedMapOf<Int, Int>())
    println("********Test set********")
    maps.forEach(::testSet)
    println("\n********Test get********")
    maps.forEach(::testGet)
    println("\n*****Test Iteration*****")
    maps.forEach(::testIteration)
}

fun testSet(map: MutableMap<Int, Int>){
    var t = 0.0
    repeat(M){ m ->
        map.clear()
        t += measure(1){
            for(i in randomArray[m]){
                map[i] = 1
            }
        }
    }
    map.clear()
    printResult(map, t / M)
}

fun testGet(map: MutableMap<Int, Int>){
    var t = 0.0
    repeat(M){ i ->
        map.clear()
        map.putAll(randomPair[i])
        val keys = map.keys.shuffled()
        t += measure(1){
            for(i in keys){
                map[i]!!
            }
        }
    }
    map.clear()
    printResult(map, t / M)
}

fun testIteration(map: MutableMap<Int, Int>){
    var t = 0.0
    repeat(M){ i ->
        map.clear()
        map.putAll(randomPair[i])
        t += measure(1){
            for((k, v) in map){
                k + v
            }
        }
    }
    map.clear()
    printResult(map, t / M)
}

fun measure(n: Int, block: (Int) -> Unit) = (1..n).map{
    System.gc()
    measureTimeMillis{
        block(it)
    }
}.average()

fun printResult(k: Any, t: Double){
    println("${k::class.simpleName}: \t$t msec")
}