Sequences

In the previous section, we saw how filtering and mapping operations can be chained together:

numbers.filter { it % 2 != 0 }.map { it * it }

In the example above, the initial filtering operation generates a temporary collection, which is then transformed by the subsequent mapping operation. After that point, the temporary collection is no longer required, and the memory it uses it will be reclaimed.

This isn’t much of a problem for the small examples that we’ve considered so far, but there could be significant performance implications to the creation of these intermediate collections if we are working with longer chains of operations, or if we are working with very large amounts of data (e.g., lists with millions of elements).

To cater for these scenarios, Kotlin provides the Sequence type¹.

A Sequence object represents a sequence of values, over which we can iterate. A Sequence object knows how to retrieve the next value in this sequence of values, without actually having to store all of the values from the sequence itself. This means that a potentially infinite series of values can be represented as a Sequence.

Because sequences are iterable, operations such as filter() and map() can be performed on sequences just as easily as on actual collections. In this way, we can avoid creation of intermediate collections when we chain operations together.

Task 8.4.1

1. Examine the file Sequences.kt, in the tasks/task8_4_1 subdirectory of your repository. You should see code like this:

   fun main() {
       val numbers = listOf(1, 4, 7, 2, 9, 3, 8)
   
       val result = numbers   // make changes here
   
       println(result)
   }
   

2. Compile the program and run it. You should see the contents of numbers displayed.

3. Add .asSequence() to the end of the second line of code in main(), after numbers. Recompile and run the program again. How has the output changed?

4. Add .filter { it % 2 != 0 } to the end of that line. Recompile and run the program again. What do you see now?

5. Add .map { it * it } to the end of the line. Recompile and run again. What has changed?

6. The filtering and mapping operations added in the previous steps did not themselves produce any data. They merely extended the sequence with additional stages of processing. To retrieve usable values from the sequence, you must add a terminal operation to it.

   Add .toList() to the end of the line, then recompile and run again. This time, you should see a list of the squares of the odd integers from numbers.

Task 8.4.2

1. The tasks/task8_4_2 subdirectory of your repository is an Amper project that explores the performance impact of using sequences. Open Benchmark.kt in the src subdirectory of this project and study the code in this file.

   The operation performed by this program involves reading lines of text from a file, filtering out the blank lines, then filtering out all the lines containing at least 10 characters, then converting the lines that remain into all lowercase.

   This operation is performed in two different ways, with and without the use of Sequence. The execution time of each implementation is measured and displayed.

2. Also in tasks/task8_4_2 is a large text file, containing the entire text of Leo Tolstoy’s notoriously long novel War And Peace. The file is over 3 MB in size and contains over 66,000 lines. Take a moment to examine its contents.

3. In a terminal window, go to the project subdirectory and then run the performance benchmark on the file, using this command:

   ./amper run war-and-peace.txt
   

1. The equivalent feature in Python is the generator. ↩