この記事は Florina Muntenescu による Android Developers - Medium の記事 "Collections and sequences in Kotlin" を元に翻訳・加筆したものです。詳しくは元記事をご覧ください。



コレクションとシーケンス

コレクションを使った処理は一般的で、Kotlin の標準ライブラリにもたくさんの便利なユーティリティ関数が準備されています。さらに、評価方法の違いによる 2 つの方法でコレクションを処理できます。すなわち、Collection を使うと積極的処理を、Sequence を使うと遅延処理を行うことができます。この記事では、この 2 つの違いに加え、どの場合にどちらを使うべきか、またそれぞれのパフォーマンスへの影響について説明します。

コレクションとシーケンス

積極的評価と遅延評価の違いは、コレクションに対する変換が実行される タイミング にあります。
コレクションは 積極的 に評価されます。つまり、各操作は呼び出されたときに実行され、その結果が新しいコレクションに格納されます。コレクションに対する変換は、インライン関数です。例として、map がどのように実装されているかを見てみると、新しい ArrayList を作成するインライン関数であることがわかります。
public inline fun <T, R> Iterable<T>.map(transform: (T) -> R): List<R> {
  return mapTo(ArrayList<R>(collectionSizeOrDefault(10)), transform)
}
シーケンスは 遅延 評価されます。シーケンスには、中間操作と末端操作の 2 とおりの操作があります。中間操作は即時実行されず、単に格納されるだけです。末端操作が呼び出されると、各要素に対して順番に中間操作が呼び出され、最後に末端操作が適用されます。中間操作（map、distinct、groupBy など）は別のシーケンスを返しますが、末端操作（first、toList、count など）はシーケンスを返しません。
シーケンスは集合内のアイテムへの参照は保持していません。シーケンスは元となるコレクションのイテレータから作られ、実行する必要があるすべての中間操作への参照を保持しています。
コレクションに対する変換とは異なり、シーケンスの中間操作による変換はインライン関数ではありません。インライン関数は格納することができませんが、シーケンスは変換処理を格納しなければなりません。map などの中間操作がどのように実装されているかを見てみると、新しい Sequence インスタンスの中に変換関数が格納されていることがわかります。
public fun <T, R> Sequence<T>.map(transform: (T) -> R): Sequence<R>{      
   return TransformingSequence(this, transform)
}
first などの末端操作は、述部条件に該当するまで、シーケンスの要素に対して反復処理を行います。
public inline fun <T> Sequence<T>.first(predicate: (T) -> Boolean): T {
   for (element in this) if (predicate(element)) return element
   throw NoSuchElementException(“Sequence contains no element matching the predicate.”)
}
TransformingSequence（上の map で使われています）などのシーケンスの実装方法を見てみると、シーケンスのイテレータから next が呼ばれたタイミングで、格納されている変換も適用されていることがわかります。
internal class TransformingIndexedSequence<T, R> 
constructor(private val sequence: Sequence<T>, private val transformer: (Int, T) -> R) : Sequence<R> {
override fun iterator(): Iterator<R> = object : Iterator<R> {
   …
   override fun next(): R {
     return transformer(checkIndexOverflow(index++), iterator.next())
   }
   …
}
Kotlin 標準ライブラリでは、使っているのがコレクションかシーケンスかによらず、両方に対して find、filter、groupBy などの非常に幅広いオペレーションが提供されています。そのため、独自の操作を実装する前に、オペレーションを確認するようにしましょう。





コレクションとシーケンス

さまざまな図形を表すオブジェクトのリストがあるとします。それらの図形を黄色にした上で、最初に登場する正方形を探す場合を考えてみましょう。

コレクションとシーケンスにそれぞれの操作が適用される方法とタイミングを確認します。

コレクション

  • map の呼び出し — 新しい ArrayList が作成されます。最初のコレクションにあるすべてのアイテムに対して反復処理を行い、元のオブジェクトをコピーして色を変えることにより、変換を行います。次に、その結果を新しいリストに追加します。
  • first の呼び出し — 最初の正方形が見つかるまで、各アイテムの反復処理を行います。

シーケンス

  • asSequence — 元となるコレクションのイテレータからシーケンスが作成されます。
  • map の呼び出し — シーケンスが実行しなければならない操作リストに変換が追加されますが、操作自体は実行されません。
  • first の呼び出し — これは末端操作なので、コレクションの各要素に対してすべての中間操作が呼び出されます。最初のコレクションに対して反復処理を行い、各アイテムに map と first をこの順番で適用します。2 つ目の要素で first の条件が満たされるので、コレクションの残りの要素に対して map が適用されることはありません。
シーケンスを使う場合、中間コレクションは作成されません。アイテムが 1 つずつ評価されるので、map は入力の一部に対してのみ実行されます。




コレクションとシーケンス — 積極的評価と遅延評価

パフォーマンス

変換の順番

大事なのは変換の順番です。この点は、コレクションとシーケンスのどちらを使うかにはよりません。先ほどの例は map 変換の結果ではないので、map を実行した後に first を実行する必要はありません。ビジネス ロジックの順番を逆転させ、コレクションに対して first を呼び出してからその結果を変換する場合でも、作成されるのは新しいオブジェクトである黄色い正方形 1 つだけです。シーケンスを使う場合は 2 つの新しいオブジェクトを作ることは避け、コレクションを使う場合はリスト全体を作ることを避けます。




変換の順番が重要 — 不要な処理を避ける

シーケンスを使うと、末端操作によって処理を切り上げることができる可能性があり、中間操作は遅延評価されるので、コレクションを使う場合に比べて不要な操作を省略できる可能性があります。変換の順番と変換同士の依存性について、常に確認するようにしましょう。

大きなデータセットをインライン化することによる影響

コレクション操作はインライン関数を使用しています。そのため、操作のバイトコードと、それに渡されるラムダ式のバイトコードがインライン化されます。シーケンスはインライン関数を使わないので、操作のたびに新しい Function オブジェクトが作成されます。
コレクションではすべての変換に対して新しいリストが作成されますが、シーケンスでは変換関数への参照が保持されるだけです。
1 つか 2 つの操作がある小さなコレクションを処理する場合、この違いによって大きな影響が生じることはありません。そのため、コレクションを使っても問題はないはずです。しかし、中間コレクションの作成を伴う大きなリストの処理は、大きな負荷となる可能性があります。そのような場合は、シーケンスを使うようにします。
残念ながら、コレクションやオペレーション チェーンのサイズがコレクションやシーケンスのパフォーマンスに与える影響について調査したベンチマークはないようです。
コレクションはデータを積極的に評価しますが、シーケンスは遅延評価します。データのサイズに応じて、最適なものを選ぶようにしましょう。小さなリストにはコレクションを、大きなリストにはシーケンスを使い、変換の順序に注意するようにしてください。

Reviewed by Yuichi Araki - Developer Relations Team