Image for post
Image for post
Collections vs sequences

Collections and sequences in Kotlin

Florina Muntenescu
Jul 24, 2019 · 5 min read

Working with collections is a common task and the Kotlin Standard Library offers many great utility functions. It also offers two ways of working with collections based on how they’re evaluated: eagerly — with Collections, and lazily — with Sequences. Continue reading to find out what’s the difference between the two, which one you should use and when, and what the performance implications of each are.

Collections vs sequences

Collections are eagerly evaluated — each operation is performed when it’s called and the result of the operation is stored in a new collection. The transformations on collections are inline functions. For example, looking at how map is implemented, we can see that it’s an inline function, that creates a new ArrayList:

public inline fun <T, R> Iterable<T>.map(transform: (T) -> R): List<R> {
return mapTo(ArrayList<R>(collectionSizeOrDefault(10)), transform)
}

Sequences are lazily evaluated. They have two types of operations: intermediate and terminal. Intermediate operations are not performed on the spot; they’re just stored. Only when a terminal operation is called, the intermediate operations are triggered on each element in a row and finally, the terminal operation is applied. Intermediate operations (like map, distinct, groupBy etc) return another sequence whereas terminal operations (like first, toList, count etc) don’t.

Sequences don’t hold a reference to the items of the collection. They’re created based on the iterator of the original collection and keep a reference to all the intermediate operations that need to be performed.

Unlike transformations on collections, intermediate transformations on sequences are not inline functions — inline functions cannot be stored and sequences need to store them. Looking at how an intermediate operation like map is implemented, we can see that the transform function is kept in a new instance of a Sequence:

public fun <T, R> Sequence<T>.map(transform: (T) -> R): Sequence<R>{      
return TransformingSequence(this, transform)
}

A terminal operation, like first, iterates through the elements of the sequence until the predicate condition is matched.

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.”)
}

If we look at how a sequence like TransformingSequence (used in the map above) is implemented, we’ll see that when next is called on the sequence iterator, the transformation stored is also applied.

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())
}

}

Independent on whether you’re using collections or sequences, the Kotlin Standard Library offers quite a wide range of operations for both, like find, filter, groupBy and others. Make sure you check them out, before implementing your own version of these.

Image for post
Image for post

Collections and sequences

Collections vs sequences

Let’s see how and when each operation is applied for collections and when for sequences

Collections

  • first is called — we iterate through each item until the first square is found

Sequences

  • map is called — the transformation is added to the list of operations needed to be performed by the sequence but the operation is NOT performed
  • first is called — this is a terminal operation, so, all the intermediate operations are triggered, on each element of the collection. We iterate through the initial collection applying map and then first on each of them. Since the condition from first is satisfied by the 2nd element, then we no longer apply the map on the rest of the collection.

When working with sequences no intermediate collection is created and since items are evaluated one by one, map is only performed on some of the inputs.

Image for post
Image for post
Collections vs sequences — eager vs lazy evaluation

Performance

Order of transformations

Image for post
Image for post
Order of transformations matters — avoid unnecessary work

Because terminal operations can finish processing early, and intermediate operations are evaluated lazily, sequences can, in some cases, help you avoid doing unnecessary work compared to collections. Make sure you always check the order of the transformations and the dependencies between them!

Inlining and large data sets consequences

On the other hand, collections create a new list for every transformation while sequences just keep a reference to the transformation function.

When working with small collections, with 1–2 operators, these differences don’t have big implications so working with collections should be ok. But, when working with large lists the intermediate collection creation can become expensive; in such cases, use sequences.

Unfortunately, I’m not aware of any benchmarking study done that would help us get a better understanding on how the performance of collections vs sequences is affected with different sizes of collections or operation chains.

Collections eagerly evaluate your data while sequences do so lazily. Depending on the size of your data, pick the one that fits best: collections — for small lists or sequences — for larger ones, and pay attention to the order of the transformations.

Android Developers

The official Android Developers publication on Medium

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store