Zenn
Open2

[kotlin]パフォーマンスが重要な箇所ではListよりArrayの使用を検討する

Kotlin
#
競技プログラミング
はやぶさはやぶさ

問題

val reachable = List(N) { i ->
    List(N) { j ->
        if (i == j) true else jumps[i].canJump(jumps[j], S)
    }
} // List<List<Boolean>>

(0 until N).forEach { k ->
    (0 until N).forEach { i ->
        (0 until N).forEach { j ->
            reachable[i][j] = reachable[i][j] || (reachable[i][k] && reachable[k][j])
        }
    }
}

List<Boolean>のように基本型(BasicType)をジェネリクスの型引数にすると、プリミティブ型をboxingしたオブジェクトをListに格納するようになる。Listから値を取り出して演算すると型のboxing , unboxing が行われパフォーマンスが悪くなる。

↑正直よくわかってない。KotlinとJavaの説明がごっちゃになってる。
Kotlinにboxing, unboxingといった概念があるのかよくわからない。
Javaにはある。Javaにはプリミティブ型(int, booleanなど)があり、それをラップしたクラス(Integer, Booleanなど)がある。両者を行き来することをboxing, unboxing と呼ぶ。コンパイラがうまい具合にboxing, unboxingしてくれて、基本的にプリミティブ型とラップした型の違いを意識する必要がない。だがboxing, unboxingが頻繁に行われるとパフォーマンスに悪影響がある。
cf. https://docs.oracle.com/javase/tutorial/java/data/autoboxing.html
arrayはプリミティブ型を扱えるが、Listは扱えない。なので大量のプリミティブ型を格納し演算したい場合はarrayを検討する。

同じことがKotlinにも言えるっぽい。

解決策

https://kotlinlang.org/docs/java-interop.html#java-arrays

Arrays are used with primitive datatypes on the Java platform to avoid the cost of boxing/unboxing operations.
IntArray, BooleanArray などを使うと Javaのarrayに相当し、プリミティブ型のまま扱えるので効率が良い

val reachable = Array(N) { i ->
    Array(N) { j ->
        if (i == j) true else jumps[i].canJump(jumps[j], S)
    }
}

(0 until N).forEach { k ->
    (0 until N).forEach { i ->
        (0 until N).forEach { j ->
            reachable[i][j] = reachable[i][j] || (reachable[i][k] && reachable[k][j])
        }
    }
}

参考