Коллекции и последовательности в Kotlin

Перевод https://typealias.com/guides/when-to-use-sequences/

Один из наиболее часто задаваемых мне вопросов звучит так. Когда я должен использовать коллекции(collections), а когда последовательности(sequences)? В данной статье я постараюсь дать ответ на этот вопрос. Мы обратим внимание на плюсы и минусы каждого подхода, включая детали, которые могут влиять на производительность.
А также взглянем на Kotlin sequences в сравнении с Java Stream API.

Cartoon of mice and an elephant on a seesaw, with mice weighing more.

Если вы задаете себе вопрос. Что такое Kotlin sequence? Вам вероятнее всего необходимо ознакомиться с этой статьей.

Sequences vs. Collections: Производительность

Производительность — дело тонкое. Да, последовательности известны тем, что имеют некоторые плюсы в сравнении с коллекциями. Но есть некоторые нюансы, которые могут быть в новинку, если вы еще с ними не сталкивались. Фактически — коллекции во многих ситуациях бывают более эффективны, нежели последовательности!

Здесь играет роль несколько факторов, которые могут влиять на производительность. Они словно грузу на весах. В одних ситуациях склонны перевешивать в сторону коллекций, а в других в сторону последовательностей.

Scales weighing characteristics of sequences and collections. Sometimes sequences perform better, and sometimes collections perform better.

Зная о существовании этих особенностей разработчик сможет принимать более эффективные решения в пользу использования того или иного подхода.

Это крайне необходимо для понимания. Если вы не тестируете ваш код, запуская бенчмарки, вы не можете знать наверняка.

Фактор 1. Количество операций

Как вы знаете, функции filter(), map(), take() доступные для использования как с коллекциями, так и с последовательностями могут быть скомбинированы в цепочку. Как показано на картинке.

The collection operation chain includes the combination of filter(), map(), take(), and toSet().

Вы можете вспомнить, что такие цепочки вызовов операторов в работе с коллекциями создают промежуточную коллекцию в перерывах между операциями.

Code with lines indicating where the wasted ArrayList instances are created.

Операции с использованием последовательностей не требуют создавать промежуточную коллекцию между ними.

В случае с коллекциями, чем больше операций вы добавляете в цепочку, тем больше промежуточных коллекций создается. Если вам нужна цепочка с большим количеством операций, очевидно что ваш выбор это последовательности.

Scales showing that sequences tend to perform better when many operations are involved.

Храните в памяти, что количество промежуточных операций играет роль при выборе необходимого подхода. Все это может влиять на производительность

Фактор 2. Короткие — замыкающиеся операции

Как вы можете вспомнить, разница между коллекциями и последовательностями заключается в порядке применения каждой операции к каждому элементу. Вот диаграмма из первой статьи, показывающая то, как обрабатывается каждый элемент в цепочке вызовов

filter { … }.map { … }.take(5).toSet()

Для обоих случаев. Как с коллекциями, так и с последовательностями.

Diagrams comparing the order of operations for a collection operation chain versus a sequence operation chain.

Из — за того, что цепочка включает take(5). Использование последовательности привело к выполнению данного кода с количеством операций — 18, а в случае с использованием коллекций их число выросло до 31.

Функция take() это то что мы можем назвать — короткой замыкающей операцией(short-circuiting operation). Потому — что она может остановить выполнение сразу после того как будут удовлетворены некоторые заданные условия.

Вот еще примеры подобных функций

contains() и indexOf() — когда элемент необходимый по условию найден, нет нужды продолжать итерации. Выполнение завершается.


any()none(), иfind() — Аналогично, когда найден элемент удовлетворяющий условию предиката, нет нужды продолжать.

first() — Естесственно также нет необходимости продолжать выполнеие после получения самого первого элемента.

Эти функции обычно помогают склонить чашу весов в сторону последовательностей из — за их меньшей затратности в плане операций

Scales showing that sequences tend to perform better when short-circuiting operations are involved.

Фактор 3. Коллекции с изменяемым размером

Часто, когда вы закончили выполнение всех операций над данными, вы хотите сохранить результат куда — нибудь вроде List или Set.

В данном коде, когда все цвета были отображены(mapped) в черно-белый оттенок, результат сохраняется в ArrayList. Как вы уже знаете, ArrayList хранит данные в виде обычного Java массива внутри себя. Этот массив имеет фиксированный размер. Другими словами, создавая массив вы заранее указываете ему размер. В течении времени существования этого массива, его размер не будет меняться. Тем не менее, путем некоторых манипуляций размер структуры данных ArrayList изменяется в зависимости от количества хранимых элементов.

Как это работает?

Когда вы создаете новый ArrayList он уже имеет initial capacity(первоначальный размер). Вы можете ничего не передавать в конструктор, тогда будет задан размер по умолчанию(10 элементов), или же передать свое собственное значение первоначального размера. Давайте скажем что у нас есть стандартный ArrayList с 10 элементами

An ArrayList with an underlying array of size 10.

Мы можем добавить в него 10 элементов. Но что произойдет, когда мы будем добавлять 11-й элемент?

An ArrayList with no room for an eleventh item.

Создастся полностью новый массив который будет больше по размеру на 50% и старые элементы будут скопированы из старого массива.

An ArrayList creating a new array to hold more items.

ArrayList начнет использовать этот новый массив вместо старого. Теперь в нем будет место для сохранения 11-го элемента. Теперь наш ArrayList поддерживает размерность 15. Но что случится если нам снова потребуется расширить размер чтобы добавить 16-й элемент? Тоже самое. Элементы будут скопированы в новый массив, который на 50% больше старого. И так будет повторяться каждый раз при увеличении размера.

Так как же это затрагивает производительность коллекций и последовательностей?

Давайте попробуем сравнить цепочки операций

(На заметку: в версии с коллекциями не надо вызывать явно toList() так как оператор map{ } уже возвращает List).

Функция map { } — это то что мы называем isometric операцией с коллекцией. Потому что размер входной коллекции будет всегда равен размеру коллекции на выходе

В этом случае выходной ArrayList с initial capacity которая равна ArrayList на входе. В данном случае ArrayList не будет менять размер. Потому — что размер будет точно таким же.

Collection.map() knows the size of the input collection, so it creates the output ArrayList with an initial capacity of the same size: 12

Как насчет версии с последовательностями?

Так как последовательности основаны на итераторах, они не могут точно знать свой размер. Из — за этого они не могут предоставить корректное значение initial capacity для создания ArrayList. Вместо этого, когда мы вызываем метод Sequence.toList() создается ArrayList с initial capacity по умолчанию. С ростом новых элементов в последовательности массив будет менять снова и снова, пока не достигнет нужного размера, чтобы хранить все необходимые элементы

Sequence.map() creates an ArrayList with the default capacity: 12. But it's not big enough to hold the last two items, so it has to copy them to a bigger array.

Процесс создания и копирования может быть весьма дорогим, когда мы производим его многократно. Он способен повлиять на производительность. Хранение результата цепочки операций в динамической коллекции типа ArrayList может дорого стоить для последовательностей. Особенно если они хранят большое число элементов.

С другой стороны, когда вы не сохраняете результаты, последовательности не испытывают эти проблемы и они могут превосходить по производительности коллекции. Это означает что к примеру тот же forEach{} лучше подходит для последовательностей.

Sets of scales showing that sequences tend to perform better with forEach(), and collections tend to perform better with toList() and toSet().

Однако эти операции сбора данных не единственные, где изменяемые размеры коллекций могут препятствовать выполнению последовательности. Некоторые операции в середине цепочки тоже могут быть подвержены этому. Так давайте это рассмотрим.

Stateless и Statefull операции

Последовательности основаны на итераторах. Итераторы имеют возможность двигаться вперед от элемента к элементу. Это может оказаться неожиданностью, но последовательности тоже поддерживают операции сортировки.

Если итераторы могут лишь перебирать элементы по порядку, тогда как вообще возможно изменить порядок? Как вообще это может работать?

Простой ответ:

  1. Последовательность конвертируется в коллекцию
  2. Коллекция сортируется
  3. Используется итератор для обхода коллекции в качестве основы для последовательных операций

Код сортировки

Достаточно умно! Даже если sorted() сам по себе является промежуточной операцией, вызывающей toMutableList() внутри себя. Вы можете заметить какое влияние оказывают детали реализации в некоторых случаях.

Например: Вы прочитали лог файл размером 4Гб как последовательность и отсортировали его. На выходе у вас получится ArrayList размером 4Гб. Это может занимать больше памяти, чем было выделено JVM.

Класс Sequence выполняет stateful операции, что значит что есть число состояний которые он может принимать(следовательно ему нужна память, чтобы хранить эти состояния) и чем больше элементов он содержит, тем больше состояний он будет иметь.

В отличии от stateful, класс Sequence который не имеет промежуточных состояний называется stateless. У него может быть одно-два поля. То есть, если количество состояний не зависит от размера, то она все равно будет называться stateless.

Большинство операторов для работы с последовательностями являются stateless операторами. Но есть пара видов операторов которые требуют наличие состояния.

Это операторы:

  • Sorting — что предполагает наличие ArrayList
  • Distinct функции которые используют HashSet для того чтобы запоминать просмотренные элементы

Из — за того что эти операторы внутри себя создают динамические коллекции с initial capacity по умолчанию, они вынуждены склонять чашу весов в пользу коллекций.

Scales showing that sequences tend to perform better when stateless operations are involved, and collections tend to perform better when stateful operations are involved.

Коллекции и последовательности. Другие нюансы

Помимо влияния на производительность, существуют и другие различия между коллекциями и последовательностями. Да, и коллекции и последовательности включают функцию iterator(). Но коллекции дополнительно имеют такие функции как size(), isEmpty() и contains().

UML diagram showing the interfaces for Sequence and Collection. Collection includes more properties and functions.

Легко прийти к мысли. Что чем больше, тем лучше. И коллекции превосходят последовательности количеством возможных операций над ними. Но не имея этих функций, последовательности открывают другие возможности для использования. Например, не имея параметра size, последовательности свободно могут иметь неограниченное количество элементов. Фактически — вполне реально создать последовательность с неограниченным набором элементов. Поскольку последовательность должна поддерживать только итератор с методами hasNext() и next(), то до тех пор пока следующий элемент может быть создан в момент вызова этих методов он удовлетворяет своему интерфейсу. Для создания такой последовательности можно использовать генератор. Генератор — это функция которая используемая для создания элемента последовательности. Например последовательность случайный чисел можно создать следующим образом

Каждый раз, когда срабатывает функция next, итератор будет использовать результат выполнения Random.nextInt(). Эта последовательность в действительности может работать бесконечно. А если разработчику нужно указать лимит необходимых значений, то он может сделать это следующим образом

Генераторы могут отдавать элементы неограниченное количество раз. А для окончания работы необходимо просто вернуть null.

Таким образом если перед вами стоит задача генерировать значения по мере необходимости, ваш выбор это последовательность, а не коллекция.

Доступные операции

Коллекции имеют большее количество операций в сравнени с последовательностями. Так как последовательности базируются на использовании iterator(), они блестяще справляются с операциями вида first-to-last. Но вот некоторые из операторов, которые поддерживаются коллекциями и не доступны для использования в последовательностях

Другие ограничения включают в себя операции такие как

  • Slicing — обрезание
  • Reversing — переворот
  • Операции из теории множеств, такие как объединение и пересечение
  • Многие другие операции, которые получают один элемент из последовательности, например: getOrNull(), random().

Если вам необходимо что — то свое. Вы можете добавить свою функциональность расширив стандартные возможности Sequence

К примеру данная функция переворачивает последовательность. Но такое поведение противоречит основной идее последовательностей(От первого — до последнего). Конкретно в данном случае лучше рассмотреть использование коллекций, нежели переворачивать последовательность.

Сравнение последовательностей и Java Stream API

Последовательности по своему духу схожи со стримами в Java. Когда они были впервые представлены в Kotlin, они так и назывались. Так когда лучше выбрать Kotlin sequences, а когда Java Stream API?

Платформа

В зависимости от платформы на которой вы запускаете свой код, Java Stream API может быть не доступно.

  • Версия Java старше 8.
  • На Android работа с Java Stream доступна с версии 7.0
  • При разработке библиотек на языке Kotlin целесообразно придерживаться концепций принятых в языке Kotlin и использовать Sequences.

Java Parallel Streams

Самым большим преимуществом для потоков Java через последовательности Kotlin является то, что потоки могут выполняться параллельно. Последовательности не работают параллельно — в конце концов, они последовательны по определению! Параллельное управление цепочками операций сопряжено с затратами на запуск, но как только вы преодолеете эти затраты, во многих случаях их производительность будет значительно выше. Поэтому, если вы работаете на JVM и обрабатываете много данных с помощью цепочки операций, которая может работать параллельно, стоит рассмотреть параллельные потоки Java.

Итог

Хотя последовательности могут работать намного лучше, чем коллекции, есть еще огромное множество случаев, когда коллекции имеют преимущество в использовании. В этой статье мы рассмотрели основные факторы, связанные с выбором между последовательностями и коллекциями. Понимание этих факторов может помочь нам лучше понять, как могут работать наши операционные цепочки, но, в конечном счете, единственный способ по-настоящему узнать, как все будет работать, — это измерить их — и сделать это с помощью настоящего инструмента для сравнительного анализа, такого как JMH.

Happy coding!

PS. В связи с тем, что это любительский перевод статьи, если вы нашли ошибку или опечатку в статье, смело сообщайте об этом в комментариях. Это поможет нам улучшить качество перевода в будущем

Понравилась статья? Поделиться с друзьями:
Комментарии: 4
  1. Илья

    Крайне полезный контент. Спасибо автору за перевод. Много нового для себя узнал. ;-) :idea:

  2. Илья

    Было бы круто ещё с этого сайта перевести статьи.

  3. Amal007

    Хах, впервые слышу о такой штуке как последовательности. Надо будет попробовать у себя. Разобрать через отладчик. Что там внутри происходит. Крайне интересная идея. Computer science не стоит на месте

    1. msfvenom (автор)

      Это точно. Сам вот вот начал осваивать Kotlin Sequences. Рад что вам понравилось

Добавить комментарий

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: