kotlinの集合操作の計算速度

kotlinで集合を操作するためにコレクション操作関数としてintersect, subtract, unionが準備されている

サーバサイドでkotlinを用いた処理を書いているときに数十万件のリスト同士の重複を取得する処理を書く場所が出たので計算量とかって大丈夫なんだっけ？となった

tl; dr

よほど
・大規模データ
・性能的な制約が厳しい
場合でない限り大丈夫そう

intersect

使用例

    val a = listOf(1, 2, 3)
    val b = listOf(2, 3, 4)

    println(a.intersect(b)) // -> [2, 3]

集合同士の重複を取得できる

定義

public infix fun <T> Iterable<T>.intersect(other: Iterable<T>): Set<T> {
    val set = this.toMutableSet()
    set.retainAll(other)
    return set
}

内部的にはsetに変換してからretainAllしている
retainAllの実行速度はjvmによって異なる？（https://stackoverflow.com/questions/2845176/what-is-the-worst-case-big-oh-using-list-retainall）

簡単に試してみた

手元の環境で試すのが早いと思ったので↓のようなコードを書いた

    val sizeList = listOf(
        Pair(100, 100),
        Pair(1000, 1000),
        Pair(10000, 10000),
        Pair(100000, 100000),
        Pair(1000000, 1000000),
        Pair(10000000, 10000000),
        Pair(1000000, 10000),
        Pair(10000,1000000)
    )

    sizeList.forEach { listSize ->
        val lista = List(listSize.first, { it }).shuffled()
        val listb = List(listSize.second, { it }).shuffled()

        val start = Instant.now().toEpochMilli()
        lista.intersect(listb)
        val end = Instant.now().toEpochMilli()

        println(end - start)
    }

実行結果

lista	listb	end-start(ms)
100	100	5
1000	1000	2
10000	10000	10
100000	100000	67
1000000	1000000	801
10000000	10000000	14757
1000000	10000	253
10000	1000000	135

(100000, 100000) -> (10000000, 10000000)
辺りがサンプル数として適していそうだが、見ても爆発はしていない（ここだけを見るならばO(n)に近い？）
-> 常識的な範囲内で利用するなら大丈夫な模様