Why sequences matter for performance in Kotlin - Performance Analysis

Time Complexity: Why sequences matter for performance

O(n) for lists, O(k) for sequences

Understanding Time Complexity

We want to see how using sequences changes the speed of processing collections in Kotlin.

How does the way we handle data affect how long the program takes?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

val numbers = (1..1_000_000).toList()

// Using list operations
val resultList = numbers
    .filter { it % 2 == 0 }
    .map { it * 2 }
    .take(5)

// Using sequences
val resultSequence = numbers.asSequence()
    .filter { it % 2 == 0 }
    .map { it * 2 }
    .take(5)
    .toList()
    

This code filters even numbers, doubles them, and takes the first 5 results, once with lists and once with sequences.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Filtering and mapping over the collection.
• How many times: For lists, each operation loops over the entire list separately. For sequences, operations are combined and stop early after 5 items.

How Execution Grows With Input

When using lists, the program processes the whole list multiple times, so work grows a lot as the list grows.

Input Size (n)	Approx. Operations (List)
10	About 20 (two passes over 10 items)
100	About 200 (two passes over 100 items)
1000	About 2000 (two passes over 1000 items)

With sequences, the program stops early after finding 5 items, so work stays small even if the list grows.

Input Size (n)	Approx. Operations (Sequence)
10	About 5 (stops after 5 items)
100	About 5 (still stops early)
1000	About 5 (still stops early)

Pattern observation: Lists do more work as input grows, sequences do only as much as needed.

Final Time Complexity

Time Complexity: O(n) for lists, O(k) for sequences where k is the number of items taken.

This means lists process the whole input, but sequences can stop early and do less work.

Common Mistake

[X] Wrong: "Sequences always make code slower because they add overhead."

[OK] Correct: Sequences add a little overhead but can save a lot of work by stopping early and combining steps, making code faster for big data.

Interview Connect

Understanding how sequences change work done helps you write faster code and explain your choices clearly in real projects.

Self-Check

What if we replaced take(5) with take(500_000)? How would the time complexity change?

Practice

1. What is the main advantage of using Sequence in Kotlin compared to a regular List?

easy

A. It processes elements lazily, improving performance with large data.

B. It stores elements in a database automatically.

C. It converts all elements to strings immediately.

D. It requires less code to create than a list.

Solution

1. Step 1: Understand how sequences process data

   Sequences process elements one by one only when needed, not all at once.

2. Step 2: Compare with lists

   Lists process all elements eagerly, which can be slower and use more memory for large data.

3. Final Answer:

   It processes elements lazily, improving performance with large data. -> Option A

4. Quick Check:

   Lazy processing = better performance [OK]

Hint: Sequences process lazily, lists process eagerly [OK]

Common Mistakes:

• Thinking sequences store data in a database
• Confusing lazy processing with immediate conversion
• Assuming sequences need less code to create

2. Which of the following is the correct way to create a sequence from a list in Kotlin?

easy

A. val seq = list.toSequence()

B. val seq = list.asSequence()

C. val seq = Sequence(list)

D. val seq = list.sequence()

Solution

1. Step 1: Recall Kotlin sequence creation syntax

   The standard way to create a sequence from a list is using asSequence().

2. Step 2: Check each option

   val seq = list.asSequence() uses list.asSequence(), which is correct. Others are invalid or do not exist.

3. Final Answer:

   val seq = list.asSequence() -> Option B

4. Quick Check:

   Use asSequence() to convert list to sequence [OK]

Hint: Use asSequence() to convert list to sequence [OK]

Common Mistakes:

• Using toSequence() which does not exist
• Trying to call sequence() on list
• Trying to instantiate Sequence directly

3. What will be the output of this Kotlin code?

val list = listOf(1, 2, 3, 4, 5)
val result = list.asSequence()
    .map { println("Mapping $it"); it * 2 }
    .filter { println("Filtering $it"); it > 5 }
    .toList()
println(result)

medium

A. Mapping and filtering printed step-by-step, then [6, 8, 10]

B. No output except [6, 8, 10]

C. [6, 8, 10] with all mapping and filtering printed before the list

D. Compilation error due to println inside lambda

Solution

1. Step 1: Understand lazy evaluation of sequences

   Sequences process elements one by one, so map and filter print statements happen step-by-step per element.

2. Step 2: Trace the output

   For each element, "Mapping" prints, then "Filtering" prints, then next element. Finally, the filtered list [6, 8, 10] prints.

3. Final Answer:

   Mapping and filtering printed step-by-step, then [6, 8, 10] -> Option A

4. Quick Check:

   Lazy = step-by-step prints [OK]

Hint: Sequences print lazily per element, not all at once [OK]

Common Mistakes:

• Assuming all map prints happen before filter prints
• Expecting no prints due to lazy evaluation
• Thinking println causes compile error

4. Identify the problem in this Kotlin code that tries to improve performance using sequences:

val numbers = (1..5).toList()
val doubled = numbers.map { it * 2 }
val filtered = doubled.asSequence().filter { it > 5 }.toList()
println(filtered)

medium

A. toList() is missing after map, causing error.

B. Filter is applied before map, causing wrong results.

C. Sequence is created after map, so map is eager and wastes memory.

D. Sequence cannot be created from a list.

Solution

1. Step 1: Analyze the order of operations

   Mapping happens first on the list eagerly, then sequence is created only for filtering.

2. Step 2: Understand performance impact

   Because map is eager, it processes all elements immediately, losing sequence benefits.

3. Final Answer:

   Sequence is created after map, so map is eager and wastes memory. -> Option C

4. Quick Check:

   Sequence after map loses lazy benefits [OK]

Hint: Create sequence before map to keep lazy processing [OK]

Common Mistakes:

• Thinking filter order is wrong
• Expecting error due to missing toList() after map
• Believing sequence can't be made from list

5. You have a large list of numbers and want to find the sum of squares of even numbers greater than 10. Which Kotlin code snippet uses sequences best for performance?

hard

A. val sum = numbers.filter { it > 10 }
.filter { it % 2 == 0 }
.map { it * it }
.sum()

B. val sum = numbers.asSequence()
.map { it * it }
.filter { it > 10 && it % 2 == 0 }
.sum()

C. val sum = numbers.map { it * it }
.filter { it > 10 && it % 2 == 0 }
.sum()

D. val sum = numbers.asSequence()
.filter { it > 10 }
.filter { it % 2 == 0 }
.map { it * it }
.sum()

Solution

1. Step 1: Identify the correct order for filtering and mapping

   Filter first for numbers > 10 and even, then map to square to avoid unnecessary calculations.

2. Step 2: Use sequence to process lazily

   Using asSequence() before filters and map ensures lazy evaluation and better performance on large lists.

3. Final Answer:

   val sum = numbers.asSequence() .filter { it > 10 } .filter { it % 2 == 0 } .map { it * it } .sum() -> Option D

4. Quick Check:

   Sequence + filter before map = best performance [OK]

Hint: Filter before map, use sequence for lazy processing [OK]

Common Mistakes:

• Mapping before filtering wastes work
• Not using sequence loses lazy benefits
• Combining filters incorrectly after map