こんにちは。ASKULのほかほかごはんです。今回はKotlin1.6におけるCollection操作についての記事になります。
List1からList2の要素を除去する場合、Kotlinでは次のように書けます。
val result = list1 - list2
このコードはKotlin 1.6ではこう書いたほうがパフォーマンスがよくなります (とIntelliJ先生が教えてくれました 😇)
val result = list1 - list2.toSet()
しかし、Kotlin 1.5まではこのコードについてIntelliJがアドバイスをくれることはなかったはずです 🤔
これは、Kotlin 1.6の minus が Kotlin 1.5 以前とは異なり、次のように実装されているからです。
Kotlin 1.6
public operator fun <T> Iterable<T>.minus(elements: Array<out T>): List<T> { if (elements.isEmpty()) return this.toList() val other = elements.convertToSetForSetOperation() return this.filterNot { it in other } }
Kotlin 1.5
public operator fun <T> Iterable<T>.minus(elements: Array<out T>): List<T> { if (elements.isEmpty()) return this.toList() val other = elements.toHashSet() return this.filterNot { it in other } }
Kotlin 1.5までは引数のArrayを無条件でhashSetに変換していますが、1.6からは暗黙に変換せず、オプション になっています。
そのため、Listのまま引数にすると、it in otherの計算量がO(n) となり、速度に顕著な差が出ます。
だから、IntelliJがアドバイスをしてくれたんですね 🙃
ここまでのまとめ
Kotlinの変更に合わせてIntelliJは常に最適なアドバイスを提供してくれます。 しかし、IntelliJやKotlin Pluginが古いバージョンではこの警告を出してくれません。 Kotlinの変更に追従して最適なコードを維持するためには常に開発環境を最新化しておくことが重要です。 IntelliJのアドバイスに耳を傾け、品質の高いコーディングを心がけましょう！
おまけ - ベンチマーク -
ここからはおまけになります。計算量 O(n) の List - List と O(1) の List - Set でベンチマークを取りました。
JMH によるベンチマーク
| Library | Version |
|---|---|
| Java | 11.0.9 |
| Kotlin | 1.6.10 |
| jmh gradle plugin | 0.6.6 |
コード
@State(Scope.Benchmark) @OutputTimeUnit(TimeUnit.SECONDS) open class ListBenchMaker { private val list1 = (1..1000).toList().shuffled() private val list2 = (1..1000).toList().filter { it % 2 == 0 }.shuffled() @Benchmark @BenchmarkMode(Mode.Throughput) fun minusByList() { val result = list1 - list2 } @Benchmark @BenchmarkMode(Mode.Throughput) fun minusBySet() { val result = list1 - list2.toSet() } }
結果
Benchmark Mode Cnt Score Error Units ListBenchMaker.minusByList thrpt 4 3432.063 ± 796.638 ops/s ListBenchMaker.minusBySet thrpt 4 37310.410 ± 7581.103 ops/s
予想通り、単位時間あたりのScoreでminusBySetが圧勝しました 🚀
ちなみに、Javaのsubtractの場合でも同様で、toSetした方が処理が早くなります。 subtractの実装 の性質上、特にlist2の要素がlist1より大きい場合に差が顕著になります。
