К содержимому
Войти

Android Road Map

📚 Коллекции и Sequence

Почти каждый экран Android-приложения начинается с того, что список с сервера фильтруют, группируют и превращают в строки для отображения. В Kotlin для этого есть десятки операторов, и на собеседовании проверяют, понимаешь ли ты, что за ними стоит: почему List нельзя назвать неизменяемым, сколько промежуточных списков создаёт цепочка из map и filter и когда Sequence ускоряет код, а когда замедляет

🧠 Как это устроено

List только для чтения, но не неизменяемый

У каждой коллекции в Kotlin два интерфейса: List и MutableList, Set и MutableSet, Map и MutableMap. В List есть только чтение: get, size, contains, итератор. add и set живут в MutableList. Документация Kotlin называет такие интерфейсы read-only, и это точное слово: ограничение действует на ссылку, а не на объект

Под интерфейсом на JVM лежит обычная Java-коллекция. Вот что видно на запуске:

val list: List<Int> = listOf(1, 2, 3)
println(list.javaClass.name)       // java.util.Arrays$ArrayList
println(list is MutableList<*>)    // true

val hacked = list as MutableList<Int>
hacked[0] = 100
println(list)                      // [100, 2, 3]
hacked.add(4)                      // UnsupportedOperationException

listOf с несколькими элементами оборачивает массив через Arrays.asList: размер у такой обёртки фиксированный, а set работает. Каст к MutableList компилируется и проходит в рантайме, потому что для JVM интерфейсы List и MutableList — один и тот же java.util.List. listOf(1) вернёт Collections$SingletonList, emptyList() вернёт объект EmptyList из stdlib, а mutableListOf создаёт обычный java.util.ArrayList. Реализация не входит в контракт и может поменяться, полагаться на неё нельзя

Второй способ увидеть «неизменяемый» список изменённым — держать на него две ссылки:

val source = mutableListOf("a", "b")
val view: List<String> = source
source.add("c")
println(view)   // [a, b, c]

Это главная ловушка на практике. Класс отдаёт наружу List, внутри меняет тот же MutableList, и снаружи список меняется под руками у того, кто его читает. Если в это время кто-то по нему итерирует, получит ConcurrentModificationException

Как получить настоящую неизменяемость. Самый простой способ — копия: source.toList() создаёт новый список, ссылки на который больше ни у кого нет. Изменения source его не задевают. Для гарантии на уровне типов есть библиотека kotlinx.collections.immutable с интерфейсами ImmutableList и PersistentList, функциями persistentListOf() и toImmutableList(). Библиотека пока в статусе Alpha, API может меняться

Что делают основные операторы

ОператорЧто возвращаетПример
mapсписок той же длиныusers.map { it.name }
flatMapплоский список из списковorders.flatMap { it.items }
filter, filterNotподсписокitems.filter { it.inStock }
partitionпару списков: подошло и нетval (ok, rest) = items.partition { ... }
groupByMap<K, List<V>>items.groupBy { it.category }
associateByMap<K, V>, при совпадении ключа побеждает последнийusers.associateBy { it.id }
associateMap<K, V> из парitems.associate { it.id to it.price }
foldодно значение, есть начальноеitems.fold(0) { acc, it -> acc + it.price }
reduceодно значение, начальное — первый элементnums.reduce { a, b -> max(a, b) }
sumOfсумму по селекторуcart.sumOf { it.price * it.qty }
chunked(n)куски по n(1..7).chunked(3) → [[1, 2, 3], [4, 5, 6], [7]]
windowed(n)скользящие окна(1..5).windowed(3) → [[1, 2, 3], [2, 3, 4], [3, 4, 5]]

map против flatMap. map превращает каждый элемент в одно значение. Если лямбда возвращает список, получится список списков: listOf(listOf(1, 2), listOf(3)).map { it } так и останется вложенным. flatMap склеивает эти списки в один: [1, 2, 3]

fold против reduce. fold начинает с переданного значения, поэтому на пустой коллекции просто вернёт его, а тип результата может отличаться от типа элементов: сложить цены товаров в Int или собрать строку. reduce берёт первый элемент как стартовый, тип результата совпадает с типом элементов, а на пустом списке падает:

emptyList<Int>().fold(0) { a, b -> a + b }     // 0
emptyList<Int>().reduce { a, b -> a + b }      // UnsupportedOperationException: Empty collection can't be reduced.
emptyList<Int>().reduceOrNull { a, b -> a + b } // null

groupBy и associateBy возвращают LinkedHashMap, поэтому ключи идут в порядке первого появления. Если нужен порядок по ключу, добавь toSortedMap()

Коллекции считают поэтапно, Sequence — поэлементно

Операторы над List жадные: каждый проходит весь список и создаёт новый. map на миллион элементов выделит массив на миллион ссылок, следующий filter — ещё один. Sequence ленивая: промежуточные операции только собирают цепочку, а считает всё терминальная операция (toList, first, count, forEach), и каждый элемент проходит цепочку целиком, прежде чем возьмут следующий

listOf(1, 2, 3)
    .map { println("map $it"); it * 10 }
    .filter { println("filter $it"); it > 10 }
// map 1, map 2, map 3, filter 10, filter 20, filter 30

listOf(1, 2, 3).asSequence()
    .map { println("map $it"); it * 10 }
    .filter { println("filter $it"); it > 10 }
    .toList()
// map 1, filter 10, map 2, filter 20, map 3, filter 30

Без терминальной операции у Sequence не выполнится ни одна лямбда: asSequence().map { ... } вернёт объект TransformingSequence, и всё

Когда Sequence быстрее. Когда цепочка длинная, данных много и результат нужен не весь. На запуске с миллионом элементов map с последующим first { it > 10 } у списка вызвался 1 000 000 раз, у Sequence — 6 раз. То же с take(n), any, find: ленивая цепочка останавливается, как только ответ найден. Плюс нет промежуточных списков, это меньше работы для сборщика мусора

Когда Sequence медленнее или бесполезна. Документация Kotlin прямо предупреждает о накладных расходах ленивости на маленьких коллекциях и простых вычислениях. Каждый шаг — отдельный объект-обёртка и вызов через итератор, а у списка из 20 элементов промежуточные массивы почти ничего не стоят. Операторы над List к тому же inline, лямбда встраивается в цикл, а лямбды Sequence остаются объектами

Вторая граница — операции с состоянием: sorted, sortedBy, distinct. Отсортировать, не увидев все элементы, нельзя, поэтому sorted в середине цепочки прогоняет через себя всё, что пришло сверху, даже если после неё стоит first():

listOf(3, 1, 2).asSequence()
    .map { println("map $it"); it }
    .sorted()
    .map { println("after sort $it"); it }
    .first()
// map 3, map 1, map 2, after sort 1

После sorted ленивость возвращается: второй map вызвался один раз. Но выигрыш от first до сортировки потерян

Обычная Sequence переиспользуется: каждая терминальная операция проходит её заново, с самого начала. Исключение — последовательности над одноразовым источником, например iterator().asSequence(): второй проход бросит IllegalStateException с текстом This sequence can be consumed only once., поэтому для повторного прохода такую последовательность сначала собирают в список

Array и List, IntArray и Array<Int>

Array<T> — массив фиксированного размера, всегда изменяемый, без read-only варианта. == у массивов сравнивает ссылки: arrayOf(1, 2) == arrayOf(1, 2) даст false, для сравнения содержимого есть contentEquals, для печати — contentToString. List сравнивается по содержимому и может быть только для чтения. Документация советует брать коллекции по умолчанию, а массивы — для Java-interop и мест, где важна производительность

Array<Int> на JVM — это Integer[], массив ссылок на объекты, каждый Int в нём упакован (боксинг). IntArray — это int[], числа лежат подряд без обёрток. Запуск подтверждает: имя класса у intArrayOf(1, 2, 3) равно [I, у arrayOf(1, 2, 3) равно [Ljava.lang.Integer;. То же с List<Int>: внутри ArrayList лежат объекты Integer. На миллионе чисел разница — миллион лишних объектов в куче, поэтому для пикселей, сэмплов звука и буферов берут IntArray, FloatArray, ByteArray. IntArray не наследник Array<Int>, перевести одно в другое можно через toTypedArray() и toIntArray()

🛠️ На практике

Типичная задача: каталог товаров с сервера нужно отфильтровать по поиску и наличию, разбить на секции по категориям и отсортировать внутри секции по цене. Результат — плоский список строк для RecyclerView или LazyColumn

Kotlin · Секции каталога из списка товаров

data class Product(val id: Long, val title: String, val category: String, val price: Int, val inStock: Boolean)

sealed interface Row {
    data class Header(val title: String, val count: Int) : Row
    data class Item(val id: Long, val title: String, val price: Int) : Row
}

fun buildRows(products: List<Product>, query: String): List<Row> =
    products
        .filter { it.inStock && it.title.contains(query, ignoreCase = true) }
        .groupBy { it.category }
        .toSortedMap()
        .flatMap { (category, items) ->
            listOf(Row.Header(category, items.size)) +
                items.sortedBy { it.price }.map { Row.Item(it.id, it.title, it.price) }
        }

// Латте 320 и Капучино 290 в «Кофе», Раф не в наличии, Круассан 210 в «Выпечке»:
// Header(title=Выпечка, count=1)
// Item(id=4, title=Круассан, price=210)
// Header(title=Кофе, count=2)
// Item(id=2, title=Капучино, price=290)
// Item(id=1, title=Латте, price=320)

Что здесь стоит заметить:

  • функция чистая: на вход List, на выход новый List. Её легко покрыть юнит-тестом без Android, а вызывать — во ViewModel при каждом новом ответе сервера или изменении запроса
  • Sequence здесь не нужна. Товаров на экране сотни, а groupBy и sortedBy всё равно требуют пройти все элементы
  • toSortedMap() сортирует секции по названию. Без него секции шли бы в порядке первого товара каждой категории
  • в UI отдаётся новый список, а не изменённый старый. И DiffUtil, и Compose рассчитывают на то, что пришедший список больше никто не поменяет

С Compose есть тонкость, которую разберёт модуль про UI. Компилятор Compose считает List нестабильным типом, потому что не может доказать неизменяемость интерфейса. Со strong skipping, который включён по умолчанию с Kotlin 2.0.20, такой параметр сравнивается по ссылке, и документация Android советует сохранять тот же экземпляр списка между обновлениями, а не массово заменять List на ImmutableList

⚠️ Где ошибаются

Отдают наружу внутренний MutableList под типом List. val items: List<Item> get() = _items, где _items — mutableListOf(). Снаружи список меняется сам по себе, адаптер видит другие данные, чем считал, или ловит ConcurrentModificationException. Отдавай копию _items.toList() или держи неизменяемый список в var и заменяй его целиком

Считают, что listOf защищает от изменений. Java-код, который получил такой список, или каст к MutableList спокойно вызовут set. Для чужого кода read-only интерфейс ничего не гарантирует

reduce на данных, которые могут быть пустыми. Сумма по пустой корзине роняет экран с UnsupportedOperationException. Для сумм есть sumOf, для свёрток подойдёт fold с начальным значением, а если нужен именно reduce, бери reduceOrNull

asSequence() везде «для скорости». На маленьких списках это медленнее и хуже читается, а перед sorted ленивость теряет смысл. Sequence оправдана, когда данных много, цепочка длинная и есть ранняя остановка: first, take, any. Не уверен — замерь

Длинные жадные цепочки на больших данных. map, filter, map, take(10) на списке в 100 000 элементов создают три промежуточных списка и обрабатывают всё ради десяти результатов. Тут как раз помогает asSequence() или перестановка: сначала filter и take, потом дорогой map

🎯 Вопросы с собеседований

В чём разница между List и Sequence и в каком порядке выполняются операции?

Операции над List жадные: каждая проходит всю коллекцию и создаёт новый список, поэтому сначала map для всех элементов, потом filter для всех. Sequence ленивая: промежуточные операции только строят цепочку, считает терминальная, и каждый элемент проходит все шаги, прежде чем возьмут следующий. За счёт этого Sequence не создаёт промежуточных списков и может остановиться раньше на first или take. Платит она объектами-обёртками и вызовами через итератор, поэтому на маленьких коллекциях обычно медленнее

Почему List в Kotlin нельзя назвать иммутабельным?

List — интерфейс только для чтения: у ссылки этого типа нет методов изменения, но сам объект может быть изменяемым. mutableListOf под ссылкой List меняется через исходную MutableList-ссылку. А listOf на JVM возвращает Arrays.asList-обёртку, которую после каста к MutableList можно менять через set, потому что в байткоде оба интерфейса — java.util.List. Настоящая неизменяемость — это копия, на которую больше нет ссылок, или ImmutableList из kotlinx.collections.immutable

Чем map отличается от flatMap?

map превращает каждый элемент ровно в одно значение, длина результата равна длине входа. flatMap ждёт от лямбды коллекцию и склеивает все коллекции в один плоский список. Например, orders.map { it.items } даст список списков, а orders.flatMap { it.items } — все товары из всех заказов одним списком

Чем fold отличается от reduce?

fold принимает начальное значение аккумулятора, поэтому работает на пустой коллекции и может вернуть другой тип, например собрать список строк в Int. reduce берёт первый элемент как стартовый, тип результата совпадает с типом элементов, а на пустой коллекции бросает UnsupportedOperationException. Если пустота возможна, беру fold или reduceOrNull

Чем IntArray отличается от Array<Int>?

IntArray компилируется в Java-массив int[]: числа лежат подряд, без объектов. Array<Int> — это Integer[], каждый элемент упакован в объект, это лишняя память и нагрузка на сборщик мусора. IntArray не наследник Array<Int>, между ними конвертируют через toTypedArray() и toIntArray(). Для больших массивов чисел беру примитивные массивы, для остального обычно List

Чем Sequence отличается от Java Stream?

Оба ленивые и считают поэлементно. Stream одноразовый: повторная терминальная операция бросит IllegalStateException, а обычную Sequence можно пройти много раз. У Stream есть параллельное выполнение, у Sequence нет. На Android java.util.stream доступен с API 24 или через desugaring библиотек, а Sequence — часть stdlib Kotlin и работает везде

Почему sorted в середине Sequence убивает выгоду от first?

sorted — промежуточная операция с состоянием: чтобы отдать первый элемент, ей нужно увидеть все. Поэтому всё, что стоит до неё, выполнится для каждого элемента, даже если в конце first(). После sorted цепочка снова ленивая. То же с distinct, ему приходится помнить все уже виденные элементы

Что будет, если сравнить два массива через ==?

У массивов == сравнивает ссылки, поэтому arrayOf(1, 2) == arrayOf(1, 2) вернёт false. Для содержимого есть contentEquals, для вложенных массивов — contentDeepEquals. Та же история с toString, он печатает что-то вроде [I@1b6d3586, поэтому для печати нужен contentToString. Списки сравниваются по содержимому, ещё одна причина брать их по умолчанию

📚 Что почитать

  • Sequences — официальная страница с примерами порядка вычислений и предупреждением о накладных расходах
  • Collections overview — чем интерфейсы только для чтения отличаются от изменяемых и неизменяемых коллекций
  • Arrays — примитивные массивы, боксинг и сравнение массивов с коллекциями
  • kotlinx.collections.immutable — неизменяемые и persistent-коллекции, если нужна гарантия на уровне типов