KotlinのListとSequenceって何が違うの？

KotlinのListとSequenceの違いについてまとめました。
一見するとほぼ同じ役割を持っているクラスに見えますが、裏側の動きは根本的に違います。
Sequenceでは関数をチェーンで繋げた場合、効率的に処理を実行することができます。

#KotlinのListとSequenceの違い
下記のサンプルコードを御覧ください。
サンプルコードではlistの関数をチェーンで繋げて、filter, filter, map, take の処理を実施しています。
resultListとresultSequenceはどちらも同じ結果（[2, 4, 6]のList）になります。

fun main(args: Array<String>) {
    val list = (1..1000000).toList()
    val resultList = list
            .filter { it < 500000 }
            .filter { it % 2 == 0 }
            .map { it.toString() }
            .take(3)

    val resultSequence = list
            .asSequence() // Sequenceに変換
            .filter { it < 500000 }
            .filter { it % 2 == 0 }
            .map { it.toString() }
            .take(3)
            .toList() // Listに変換
}

resultSequenceの方はlistをSequenceに変換して、処理後にListに戻しています。
一見すると無駄な処理に見えますが、この例の場合はListと比較するとSequenceの方が処理速度が早くなります。
その理由について見ていきましょう。

##Listの場合の操作
こちらのListの場合の操作について見ていきます。

fun main(args: Array<String>) {
    val list = (1..1000000).toList()
    val resultList = list
            .filter { it < 500000 }
            .filter { it % 2 == 0 }
            .map { it.toString() }
            .take(3)
}

Listの場合は関数のチェーンの上から順番にすべての値に対して操作が実行されます。

1. 500000より小さいリストを生成
2. 偶数のリストを生成
3. Stringに変換したリストを生成
4. 先頭から3つの値のリストを生成

最終的に欲しい値は先頭から3つの値だけで良いのに対して、
1.では100万件、2.では約50万件、3.では約25万件の値に対して処理を実行しています。
なんだか無駄な処理をしている気がしませんか？
そこでSequenceの出番です。

##Sequenceの場合の操作
こちらのSequenceの場合の操作について見ていきます。

fun main(args: Array<String>) {
    val list = (1..1000000).toList()
    val resultSequence = list
            .asSequence() // Sequenceに変換
            .filter { it < 500000 }
            .filter { it % 2 == 0 }
            .map { it.toString() }
            .take(3)
            .toList() // Listに変換
}

この例のSequenceの場合は、filter, filter, map, take　は中間操作として扱われます。
また、toListは終端操作になります。
中間操作は終端操作が呼び出されるまで実行されることはありません。
これを遅延評価と言います。
（中間操作と終端操作に関しては別の記事にしたいと思います。）

Sequenceは以下のように値ごとに処理を実施していきます。
list[0]の値の処理を実施 → list[1]の値の処理を実施 → list[2]の値の処理を実施 → ...

このように値ごとに処理を実施することで、list[5]の処理を実施した時点で、resultSequenceの結果（[2, 4, 6]のList）を求めることができます。
結果を求められた時点で、それ以降の処理は実施しません。
つまり、list[6]以降の処理は実行されないので、Listと比較して処理が高速化されます。

##実測値
手元のマシンで実測したところ、Listの方は100ms程度、Sequenceの方は15ms程度で処理が終了しました。
100万件のリストで実測すると顕著な違いが出ました。

ちなみに100件のリストで試したところ、Listの方は1ms程度、Sequenceの方は10ms程度で処理が終了しました。
恐らくasSequence()やtoList()のコスト分Sequenceの方が遅くなったのかと思います。

実行環境

環境	詳細
macOS High Sierra	ver.10.13.6
プロセッサ	Intel Core i7 3.5GHz
メモリ	16GB

#まとめ

• ListとSequenceは似ているけど裏側の処理は根本的に違います
• Listはすべての値に対して上から操作を実施します
• Sequenceは値を順番に処理して、結果が出た時点で処理を終了します
• 大量件数のリストを関数のチェーンで操作する場合はSequenceにすることで処理効率を上げられます