Остерегайтесь привычек Java Stream API при написании кода Kotlin

Kotlin Collections API чрезвычайно универсален и выразителен, но есть одна важная вещь, о которой следует помнить, особенно при переходе с Java.

Болезненный дизайн коллекций Java

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

Например, представьте, что вы реализуете новую неизменяемую структуру данных для Java и пытаетесь реализовать следующие методы:

boolean add(E e);
boolean remove(Object o);
void clear();
boolean removeAll(Collection<?> c);
// ...

Единственный разумный способ — просто запретить их использование:

public E set(int index, E element) {
    throw new UnsupportedOperationException();
}
public void add(int index, E element) {
    throw new UnsupportedOperationException();
}
public E remove(int index) {
    throw new UnsupportedOperationException();
}
// and so on ...

И так будет всегда, пока в Java реализована обратная совместимость (хотя в последних релизах это было не очень хорошо).

Это одна из причин, по которой единственным разумным способом обогатить API было введение новой абстракции — Stream API. Потоки не являются коллекциями, поэтому API можно разрабатывать с нуля.

Ленивый API потоковой передачи

Помимо нового причудливого функционального API, основным преимуществом java.util.stream.Stream была ленивость, которая делала их почти такими же производительными, как стандартные императивные решения, и позволяла работать с потенциально бесконечными последовательностями.

Рассмотрим следующий пример:

Optional<Integer> resultStream = list.stream()
  .map(i -> i * 2)
  .filter(i -> i > 1)
  .findAny();

Сначала может возникнуть соблазн подумать, что оптимистичная временная сложность равна O(2*N), в то время как императивная альтернатива обеспечивает O(1), будучи менее подверженной ошибкам и менее читабельной:

Optional<Integer> resultLoop = Optional.empty();
for (Integer i : list) {
    Integer integer = i * 2;
    if (integer > 1) {
        resultLoop = Optional.of(integer);
        break;
    }
}

Даже значительного улучшения в ремонтопригодности/читабельности кода недостаточно, чтобы оправдать влияние на производительность.

К счастью, благодаря ленивому вычислению оба примера обеспечивают оптимистическую временную сложность O(1) (совпадает первый встреченный элемент) и пессимистическую O(N) (нет совпадений элементов). Потоки просто берут элементы один за другим и проталкивают их. вся операционная цепочка, позволяющая закоротить, как только будет получен результат.

Ловушка API экспрессивных коллекций Kotlin

Kotlin Collections API чрезвычайно универсален, выразителен и хорошо подходит для работы с неизменяемыми структурами данных — звучит здорово, правда? Но они, безусловно, могут иметь неприятные последствия, если их неправильно использовать!

Отличительной особенностью коллекций в Kotlin является то, что они неизменяемы по умолчанию и имеют очень богатый функциональный API, поэтому нам больше не нужно обращаться к Stream API, поскольку наши коллекции уже предоставляют всю эту функциональность.

Итак, если бы мы попытались воссоздать приведенный выше пример, мы могли бы просто написать:

val list = listOf(1, 2, 3, 4, 5)

list
  .map(expensiveOperation())
  .map(anotherExpensiveOperation())
  .first()

Красиво и чисто, но есть одна загвоздка — давайте измерим время выполнения.

Как вы думаете, что будет в результате, если предположить, что и дорогаяОперация(), и другаяЭкспенсивнаяОперация() длятся ровно одну секунду?

Коллекции Kotlin не ленивы, поэтому операция заняла около 10 секунд, что соответствует оптимистичной временной сложности O (2 * N), где N = 5.

С большой силой приходит и большая ответственность — добавление каждого нового вызова map/flatMap/filter/… может негативно сказаться на временной сложности вашего решения в определенных сценариях, потому что каждый из них просто создает новый экземпляр коллекции, просто перебирая предыдущий — они также не поддерживают короткое замыкание.

Возвращаем лень

Всем хороших новостей!

Естественно, Kotlin предоставил собственный способ достижения лени в ситуациях, подобных приведенным выше, путем введения ленивых последовательностей. Мы можем преобразовать каждый Iterable в ленивую Sequence, которая является альтернативой Kotlin Stream, с помощью метода asSequence():

val list = listOf(1, 2, 3, 4, 5).asSequence()

list
  .map(expensiveOperation())
  .map(anotherExpensiveOperation())
  .first()

Если мы измерим время выполнения сейчас, мы сможем вздохнуть с облегчением, потому что результат составляет около 2 секунд, независимо от исходного размера последовательности, который соответствует временной сложности O (1) (2 секунды из-за двух вызовов map()) .

Приведенные выше фрагменты кода можно найти на GitHub.