【Kotlin】take や drop などを使わない場合でも Sequence で高速化【計測】

## 1行で

`filter` や `map` などの変換関数をチェインする場合は、`take` や `drop` などで要素数を減らさない場合であっても、[`Sequence`](https://kotlinlang.org/api/latest/jvm/stdlib/kotlin.sequences/-sequence/index.html) を使うことで高速化できます。

## 詳しく

`filter` や `map` などの、[`List`](https://kotlinlang.org/api/latest/jvm/stdlib/kotlin.collections/-list/index.html) から別の [`List`](https://kotlinlang.org/api/latest/jvm/stdlib/kotlin.collections/-list/index.html) への変換関数。
これらをチェインして、変換処理を行うことはよくあるでしょう。

```Kotlin
list
    .filter { it % 2 == 0 }
    .map { it.toString() }
```

それらの変換の後で `take` や `drop` などを用いて要素数を減らすような場合は、[`Sequence`](https://kotlinlang.org/api/latest/jvm/stdlib/kotlin.sequences/-sequence/index.html) を使うことで、最終的に不要な要素に対しては `filter` や `map` などでの変換処理が適用されなくなり、大幅に効率を上げることができます。
これは [`Sequence`](https://kotlinlang.org/api/latest/jvm/stdlib/kotlin.sequences/-sequence/index.html) についてある程度ご存知の方にはよく知られていることでしょう。

```Kotlin
list
    .asSequence() // Sequence に変換
    .filter { it % 2 == 0 }
    .map {
        it.toString() // 5回までしか呼ばれない
    }
    .take(5)
```

しかし、`take` や `drop` などで要素数を減らさない場合も、[`Sequence`](https://kotlinlang.org/api/latest/jvm/stdlib/kotlin.sequences/-sequence/index.html) を使うことで高速化が図れます。

次のコードは [`Sequence`](https://kotlinlang.org/api/latest/jvm/stdlib/kotlin.sequences/-sequence/index.html) の方が高速であることを確認するコードの例です。
`filter` と `map` による変換を [`List`](https://kotlinlang.org/api/latest/jvm/stdlib/kotlin.collections/-list/index.html) と [`Sequence`](https://kotlinlang.org/api/latest/jvm/stdlib/kotlin.sequences/-sequence/index.html) それぞれに対して行い、それぞれに掛かる時間を計測します。
ガベッジコレクションのタイミングによるものか、値が大きく異なることがよくあるため、複数回の計測を行って中央の1/3だけを平均します。

```Kotlin
fun main() {
    val list = List(1000) { Any() } // 変換元のリスト

    val repeatCount = 1000
    val listTime = TimeMeasurer(repeatCount)
    val sequenceTime = TimeMeasurer(repeatCount)

    // 誤差を減らすために繰り返し交互に行う。
    repeat(1000) {
        // List のままでの変換処理の所要時間を計測する。
        listTime.measure {
            list
                .filter { true }
                .map { it }
        }

        // Sequence に変換してからの変換処理の所要時間を計測する。
        sequenceTime.measure {
            list
                .asSequence()
                .filter { true }
                .map { it }
                .toList()
        }
    }

    println("list: ${listTime.average()}")
    println("seqence: ${sequenceTime.average()}")
}

/**
 * 処理の所要時間を計測するためのクラス。
 *
 * @param repeatCount 1回の計測での繰り返し回数。
 */
class TimeMeasurer(
    private val repeatCount: Int
) {
    private val times = mutableListOf<Long>()

    fun measure(block: () -> Unit) {
        times += measureTimeMillis {
            repeat(repeatCount) {
                block()
            }
        }
    }

    fun average(): Double {
        val size = times.size
        return times
            .sorted().drop(size / 3).take(size / 3) // 上位と下位それぞれの1/3を除く
            .average() / repeatCount
    }
}
```

結果の標準出力の例：

```
list: 0.015
seqence: 0.011603603603603603
```

[`Sequence`](https://kotlinlang.org/api/latest/jvm/stdlib/kotlin.sequences/-sequence/index.html) の方が高速であることを確認できました。

[`List`](https://kotlinlang.org/api/latest/jvm/stdlib/kotlin.collections/-list/index.html) から [`List`](https://kotlinlang.org/api/latest/jvm/stdlib/kotlin.collections/-list/index.html) への変換では、関数呼び出しごとに [`List`](https://kotlinlang.org/api/latest/jvm/stdlib/kotlin.collections/-list/index.html) インスタンスが生成されます。
そしてそれらのインスタンスごとに、要素数分のメモリが確保されます。（そしてすぐ不要になります。）
[`Sequence`](https://kotlinlang.org/api/latest/jvm/stdlib/kotlin.sequences/-sequence/index.html) ではこのメモリが不要なため、高速であることが期待されます。