Help us understand the problem. What is going on with this article?

kotlinの集合操作の計算速度

More than 1 year has passed since last update.

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)に近い?)
-> 常識的な範囲内で利用するなら大丈夫な模様

sptea
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away