Scala коллекции: секреты и трюки

в 16:28, , рубрики: scala, Алгоритмы, коллекции, Программирование, функциональное программирование

Представляю вашему вниманию перевод статьи Павла Фатина Scala Collections Tips and Tricks. Павел работает в JetBrains и занимается разработкой Scala плагина для IntelliJ IDEA. Далее, повествование идет от лица автора.

В этой статье вы найдете упрощения и оптимизации, характерные для повседневного использования API Scala коллекций.

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

Этот список вдохновлен моими попытками разработать практичные инспекции для Scala коллекций, для Scala плагина IntelliJ. Сейчас мы внедряем эти инспекции, так что, используя Scala плагин в IDEA, вы автоматически выигрываете от статического анализа кода.

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

Обновление:
Если вы испытываете тягу к приключениям,
вы можете узнать, как помочь в развитии IntelliJ плагина для Scala и попробовать свои силы в реализации, подобрав подходящую инспекцию.

Содержание:

  1. Легенда
  2. Композиция
  3. Побочные эффекты
  4. Последовательности (Sequences)
    4.1. Создание
    4.2. Длина
    4.3. Равенство
    4.4. Индексация
    4.5. Существование
    4.6. Фильтрация
    4.7. Сортировка
    4.8. Свертка
    4.9. Сопоставление
    4.10. Перерабатываем
  5. Множества (Sets)
  6. Option-ы
    6.1. Значение
    6.2. Null
    6.3. Обработка
    6.4. Перерабатываем
  7. Таблицы
  8. Дополнение

Все примеры кода доступны в репозитории на GitHub.

1. Легенда

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

  • seq — экземпляр основанной на Seq коллекции, вроде Seq(1, 2, 3)
  • set — экземпляр Set, например Set(1, 2, 3)
  • array — массив, такой как Array(1, 2, 3)
  • option — экземпляр Option, например, Some(1)
  • map — экземпляр Map, подобный Map(1 -> "foo", 2 -> "bar")
  • ??? — произвольное выражение
  • p — предикат функции типа T => Boolean, например _ > 2
  • n — целочисленное значение
  • i — целочисленный индекс
  • f, g — простые функции, A => B
  • x, y — некоторые произвольные значения
  • z — начальное или значение по умолчанию
  • P — паттерн

2. Композиция

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

seq.filter(_ == x).headOption != None

// от seq.filter(p).headOption к seq.find(p)
seq.find(_ == x) != None

// от option != None к option.isDefined
seq.find(_ == x).isDefined

// от seq.find(p).isDefined к seq.exists(p)
seq.exists(_ == x)

// от seq.exists(_ == x) к seq.contains(x)
seq.contains(x)

Так, мы можем полагаться на "заменяющую модель применения рецептов" (аналогично SICP), и использовать ее для упрощения сложных выражений.

3. Побочные эффекты

"Побочный эффект" (Side effect) это основное понятие, которое стоит рассмотреть перед тем, как мы перечислим основные преобразования.

По сути, побочный эффект — любое действие, которое наблюдается за пределами функции или выражения помимо возврата значения, например:

  • операция ввода-вывода,
  • модификация переменной (доступной за пределами области видимости),
  • изменение состояния объекта (наблюдаемое вне области видимости),
  • возбуждение исключения (которое также не обрабатывается внутри области видимости).

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

Почему побочные эффекты так важны? Потому что с ними порядок исполнения имеет значение. Например, два «чистых» выражения, (связанных с соответствующими значениями):

val x = 1 + 2
val y = 2 + 3

Так как они не содержат побочных эффектов (т.е. эффектов, наблюдаемых вне выражений), мы можем вычислить эти выражения в произвольном порядке — сначала x, а затем y или сначала y, а затем x — это не повлияет на корректность полученных результатов (мы можем даже закешировать результирующие значения, если того захотим). Теперь рассмотрим следующую модификацию:

val x = { print("foo"); 1 + 2 }
val y = { print("bar"); 2 + 3 }

А это уже другая история — мы не можем изменить порядок выполнения, потому что в нашем терминале будет напечатано "barfoo" вместо "foobar" (и это явно не то, чего хотелось).

Так, присутствие побочных эффектов сокращает число возможных преобразований (как упрощений, так и оптимизаций), которые мы можем применить к коду.

Схожие рассуждения применимы и к родственным коллекциям, выражениям. Представим, что где-то за пределами области видимости у нас есть некий builder:

seq.filter(x => { builder.append(x); x > 3 }).headOption

В принципе, вызов seq.filter(p).headOption упрощается до seq.find(p), впрочем, наличие побочного эффекта не дает нам это сделать:

seq.find( x => {builder.append(x); x > 3 })

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

Что можно сделать для того, чтобы автоматическое упрощение стало возможным? Ответ — это золотое правило, которого следует придерживаться по отношению ко всем побочным эффектам в нашем коде (включая тот, где коллекций нет в принципе):

  • Избегать побочных эффектов, когда это возможно.
  • В противном случае изолировать побочные эффекты от чистого кода.

Поэтому нам нужно либо избавиться от builderа (вместе с его API, в котором есть побочные эффекты), либо отделить вызов builderа от чистого выражения. Предположим, что этот builder является неким сторонним объектом, изжить который мы не можем, так что нам остается лишь изолировать вызов:

seq.foreach(builder.append)
seq.filter(_ > 3).headOption

Теперь мы можем благополучно выполнить преобразование:

seq.foreach(builder.append)
seq.find(x > 3)

Чисто и красиво! Изоляция побочных эффектов сделала возможным автоматическое преобразование. Дополнительная выгода еще и в том, что из-за присутствия четкого разделения, человеку легче понять получившийся код.

Наименее очевидным и при этом наиболее важным преимуществом изоляции побочных эффектов будет улучшение надежности нашего кода вне зависимости от других возможных оптимизаций. Касательно примера: первоначальное выражение может порождать различные побочные эффекты, зависящие от текущей реализации Seq. Для Vector, например, оно добавит все элементы, для Stream оно пропустит все элементы после первого удачного сопоставления с предикатом (потому что стримы «ленивы» — элементы вычисляются только тогда, когда это необходимо). Отделение побочных эффектов позволяет нам избежать этих неопределенностей.

4. Последовательности (Sequences)

Хотя советы в этом разделе и относятся к наследникам Seq, некоторые преобразования допустимы и для других типов коллекций (и не коллекций), например: Set, Option, Map и даже Iterator (потому что все они предоставляют похожие интерфейсы с монадическими методами).

4.1 Создание

Явно создавайте пустые коллекции

// До
Seq[T]()

// После
Seq.empty[T]

Некоторые неизменяемые (immutable) классы коллекций имеют синглтон-реализацию метода empty. Однако, далеко не все фабричные методы проверяют длину созданных коллекций. Так что, обозначив пустоту на этапе компиляции, вы можете сохранить либо место в куче (путем переиспользования экземпляра), либо такты процессора (которые могли бы быть потрачены на проверки размерности во время выполнения).
Также применимо к: Set, Option, Map, Iterator.

4.2 Длины

Для массивов используйте length вместо size

// До
array.size

// После
array.length

Хотя size и length по существу синонимы, в Scala 2.11 вызовы Array.size по-прежнему выполняются через неявное преобразование (implicit conversion), таким образом создавая промежуточные объекты-обертки для каждого вызова метода. Если вы, конечно, не включите эскейп анализ для JVM, временные объекты станут обузой для сборщика мусора и ухудшат производительность кода (особенно внутри циклов).

Не отрицайте isEmpty

// До
!seq.isEmpty
!seq.nonEmpty

// После
seq.nonEmpty
seq.isEmpty

Простые свойства содержат меньше визуального шума, чем составные выражения.
Также применимо к: Set, Option, Map, Iterator.

Не вычисляйте длину при проверке на пустоту.

// До
seq.length > 0
seq.length != 0
seq.length == 0

// После
seq.nonEmpty
seq.nonEmpty
seq.isEmpty

С одной стороны, простое свойство воспринимается гораздо легче, чем составное выражение. С другой стороны, наследникам LinearSeq (таким как List) может потребоваться O(n) времени на вычисление длины списка (вместо O(1) для IndexedSeq), таким образом мы можем ускорить наш код, избегая вычисления длины, когда нам, вобщем-то, это значение не очень-то и нужно.
Имейте также в виду, что вызов .length для бесконечных стримов может никогда не закончиться, поэтому всегда проверяйте стрим на пустоту явно.
Также применимо к: Set, Map.

Во время сравнения не вычисляйте полный размер коллекции

// До
seq.length > n
seq.length < n
seq.length == n
seq.length != n

// После
seq.lengthCompare(n) > 0
seq.lengthCompare(n) < 0
seq.lengthCompare(n) == 0
seq.lengthCompare(n) != 0

Поскольку расчет размера коллекции может быть достаточно «дорогим» вычислением для некоторых типов коллекций, мы можем сократить время сравнения с O(length) до O(length min n) для наследников LinearSeq (которые могут быть спрятаны под Seq-подобными значениями). Кроме того, такой подход незаменим, когда имеем дело с бесконечными стримами.

Не используйте exists для проверки на пустоту

// До
seq.exists(_ => true)
seq.exists(const(true))

// После
seq.nonEmpty

Разумеется, такой трюк будет совсем излишним.
Также применимо к: Set, Option, Map, Iterator.

4.3 Равенство

Не полагайтесь на == для сравнения содержимого массивов

// До
array1 == array2

// После
array1.sameElements(array2)

Проверка на равенство всегда будет выдавать false для различных экземпляров массивов.
Также применимо к: Iterator.

Не проверяйте на равенство коллекции различных категорий

// До
seq == set

// После
seq.toSet == set

Проверки на равенство могут быть использованы для сравнения коллекций и различных категорий (например List и Set).
Прошу вас дважды подумать о смысле данной проверки (касательно примера выше — как рассматривать дубликаты в последовательности).

Не используйте sameElements для сравнения обыкновенных коллекций

// До
seq1.sameElements(seq2)

// После
seq1 == seq2

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

Не используйте corresponds явно

// До
seq1.corresponds(seq2)(_ == _)

// После
seq1 == seq2

У нас уже есть встроенный метод, который делает тоже самое. Оба выражения принимают во внимание порядок элементов. И мы опять-таки сможем выиграть пользу от повышения производительности.

4.4 Индексация

Не получайте первый элемент по индексу

// До
seq(0)

// После
seq.head

Для некоторых классов коллекций обновленный подход может быть немного быстрее (ознакомьтесь с кодом List.apply, например). К тому же, доступ к свойству намного проще (как синтаксически, так и семантически), чем вызов метода с аргументом.

Не получайте последний элемент по индексу

// До
seq(seq.length - 1)

// После
seq.last

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

Не проверяйте нахождение индекса в границах коллекции явно

// До
if (i < seq.length) Some(seq(i)) else None

// После
seq.lift(i)

Семантически второе выражение эквивалентно, однако более выразительно

Не эмулируйте headOption

// До
if (seq.nonEmpty) Some(seq.head) else None
seq.lift(0)

// После
seq.headOption

Упрощенное выражение более лаконично.

Не эмулируйте lastOption

// До
if (seq.nonEmpty) Some(seq.last) else None
seq.lift(seq.length - 1)

// После
seq.lastOption

Последнее выражение короче (и потенциально быстрее).

Будьте осторожны с типами аргументов для indexOf и lastIndexOf

// До
Seq(1, 2, 3).indexOf("1") // скомпилируется
Seq(1, 2, 3).lastIndexOf("2") // скомпилируется

// После
Seq(1, 2, 3).indexOf(1)
Seq(1, 2, 3).lastIndexOf(2)

Из-за особенностей работы вариантности, методы indexOf и lastIndexOf принимают аргументы типа Any. На практике это может приводить к труднонаходимым багам, которые невозможно обнаружить на этапе компиляции. Вот где будут к месту вспомогательные инспекции вашей IDE.

Не создавайте диапазон индексов последовательности вручную

// До
Range(0, seq.length)

// После
seq.indices

У нас есть встроенный метод, который возвращает диапазон из всех индексов последовательности.

Не используйте zip для связывания коллекции с индексами вручную

// До
seq.zip(seq.indices)

// После
seq.zipWithIndex

Во-первых, последнее выражение короче. Кроме того, мы можем ожидать некоторый прирост производительности, из-за того, что мы избегаем скрытого вычисления размера коллекции (что в случае линейных последовательностей может обойтись недешево).
Дополнительное преимущество последнего выражения в том, что оно хорошо работает с потенциально бесконечными коллекциями (например Stream).

Используйте экземпляр IndexedSeq как объект-функцию:

// До (seq: IndexedSeq[T])
Seq(1, 2, 3).map(seq(_))

// После
Seq(1, 2, 3).map(seq)

Поскольку экземпляр IndexedSeq[T] также является Function1[Int, T], вы можете использовать его как таковой.

4.5 Существование

Не используйте предикат сравнения для проверки наличия элемента

// До
seq.exists(_ == x)

// После
seq.contains(x)

Второе выражение семантически эквивалентно, при этом более выразительно. Когда эти выражения применяются к Set, производительность может разительно отличаться, потому что поиск у множеств стремится к O(1) (из-за внутреннего индексирования, не использующегося при вызове exists).
Также применимо к: Set, Option, Iterator.

Будьте осторожны с типом аргумента contains

// До
Seq(1, 2, 3).contains("1") // компилируется

// После
Seq(1, 2, 3).contains(1)

Так же как методы indexOf и lastIndexOf, contains принимает аргументы типа Any, что может привести к труднонаходимым багам, которые не обнаруживаются на этапе компиляции. Будьте с ними осторожны.

Не используйте предикат неравенства для проверки отсутствия элемента

// До
seq.forall(_ != x)

// После
!seq.contains(x)

И снова последнее выражение чище и, вероятно, быстрее (особенно для множеств).
Также применимо к: Set, Option, Iterator.

Не считайте вхождения для проверки существования

// До
seq.count(p) > 0
seq.count(p) != 0
seq.count(p) == 0

// После
seq.exists(p)
seq.exists(p)
!seq.exists(p)

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

  • Предикат p должен быть чистой функцией.
  • Также применимо к: Set, Map, Iterator.

Не прибегайте к фильтрации для проверки существования

// До
seq.filter(p).nonEmpty
seq.filter(p).isEmpty

// После
seq.exists(p)
!seq.exists(p)

Вызов filter создает промежуточную коллекцию, которая занимает место в куче и нагружает GC. К тому же, предшествующие выражения находят все вхождения, в то время как требуется найти только первое (что может замедлить код в зависимости от возможного содержимого коллекции). Потенциальный выигрыш в производительности менее значим для ленивых коллекций (таких как Stream и, в особенности, Iterator).

  • Предикат p должен быть чистой функцией.
  • Также применимо к: Set, Option, Map, Iterator.

Не прибегайте к поиску, чтобы проверить существование

// До
seq.find(p).isDefined
seq.find(p).isEmpty

// После
seq.exists(p)
!seq.exists(p)

Поиск определенно лучше фильтрации, однако и это далеко не предел (по крайней мере, с точки зрения ясности).
Также применимо к: Set, Option, Map, Iterator.

4.6 Фильтрация

Не отрицайте предикат filter

// До
seq.filter(!p)

// После
seq.filterNot(p)

Последнее выражение синтактически проще (при том, что семантически они эквивалентны).
Также применимо к: Set, Option, Map, Iterator.

Не фильтруйте, чтобы посчитать

// До
seq.filter(p).length

// После
seq.count(p)

Вызов filter создает промежуточную (и не очень-то нужную) коллекцию, которая будет занимать место в куче и нагружать GC.
Также применимо к: Set, Option, Map, Iterator.

Не используйте фильтрацию для того, чтобы найти первое вхождение

// До
seq.filter(p).headOption

// После
seq.find(p)

Конечно, если seq не является ленивой коллекцией (как, например, Stream), фильтрация найдет все вхождения (и создаст временную коллекцию) при том, что требовался только первый элемент.
Также применимо к: Set, Option, Map, Iterator.

4.7 Сортировка

Не сортируйте по свойству вручную

// До
seq.sortWith(_.property <  _.property)

// После
seq.sortBy(_.property)

Для этого у нас есть свой метод, более ясный и выразительный.

Не сортируйте по тождеству вручную

// До
seq.sortBy(identity)
seq.sortWith(_ < _)

// После
seq.sorted

И для этого тоже есть метод.

Выполняйте обратную сортировку в один шаг

// До
seq.sorted.reverse
seq.sortBy(_.property).reverse
seq.sortWith(f(_, _)).reverse

// После
seq.sorted(Ordering[T].reverse)
seq.sortBy(_.property)(Ordering[T].reverse)
seq.sortWith(!f(_, _))

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

Не используйте сортировку для нахождения минимального элемента

// До
seq.sorted.head
seq.sortBy(_.property).head

// После
seq.min
seq.minBy(_.property)

Последний подход более выразителен. Кроме того, из-за того что не создается дополнительная коллекция, работать он будет быстрее.

Не используйте сортировку для нахождения максимального элемента

// До
seq.sorted.last
seq.sortBy(_.property).last

// После
seq.max
seq.maxBy(_.property)

Объяснение совпадает с предыдущим советом.

4.8 Свертка

Не вычисляйте сумму вручную

// До
seq.reduce(_ + _)
seq.fold(z)(_ + _)

// После
seq.sum
seq.sum + z

Преимущества этого подхода — ясность и выразительность.

  • Другие возможные методы: reduceLeft, reduceRight, foldLeft, foldRight.
  • Второе преобразование может быть заменено первым, если z равняется 0.
  • Также применимо к: Set, Iterator.

Не вычисляйте произведение вручную

// До
seq.reduce(_ * _)
seq.fold(z)(_ * _)

// После
seq.product
seq.product * z

Причины те же, что и в предыдущем случае.

  • Второе преобразование может быть заменено первым, если z равняется 1.
  • Также применимо к: Set, Iterator.

Не ищите минимальный элемент вручную

// До
seq.reduce(_ min _)
seq.fold(z)(_ min _)

// После
seq.min
z min seq.min

Обоснование такое же, как и в предыдущем случае.
Также применимо к: Set, Iterator.

Не выполняйте поиск максимального элемента вручную

// До
seq.reduce(_ max _)
seq.fold(z)(_ max _)

// После
seq.max
z max seq.max

Все как и в предыдущем случае.
Также применимо к: Set, Iterator.

Не эмулируйте forall

// До
seq.foldLeft(true)((x, y) => x && p(y))
!seq.map(p).contains(false)

// После
seq.forall(p)

Цель упрощения — ясность и выразительность.

  • Предикат p должен быть чистой функцией.
  • Также применимо к: Set, Option (для второй строки), Iterator.

Не эмулируйте exists

// До
seq.foldLeft(false)((x, y) => x || p(y))
seq.map(p).contains(true)

// После
seq.exists(p)

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

  • Предикат p должен быть чистой функцией.
  • Также применимо к: Set, Option (для второй строки), Iterator.

Не эмулируйте map

// До
seq.foldLeft(Seq.empty)((acc, x) => acc :+ f(x))
seq.foldRight(Seq.empty)((x, acc) => f(x) +: acc)

// После
seq.map(f)

Это «классическая» в функциональном программировании реализация отображения (map) через свертку. Бесспорно, она поучительна, но нужды ее использовать нет. Для этого у нас есть встроенный и выразительный метод (который еще и быстрее, так как в своей реализации использует простой цикл while).
Также применимо к: Set, Option, Iterator.

Не эмулируйте filter

// До
seq.foldLeft(Seq.empty)((acc, x) => if (p(x)) acc :+ x else acc)
seq.foldRight(Seq.empty)((x, acc) => if (p(x)) x +: acc else acc)

// После
seq.filter(p)

Причины те же, что и в предыдущем случае.
Также применимо к: Set, Option, Iterator.

Не эмулируйте reverse

// До
seq.foldLeft(Seq.empty)((acc, x) => x +: acc)
seq.foldRight(Seq.empty)((x, acc) => acc :+ x)

// После
seq.reverse

И опять-таки встроенный метод быстрее и чище.
Также применимо к: Set, Option, Iterator.

4.9 Сопоставление

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

Используйте частичные функции вместо функций с паттерн-матчингом

// До
seq.map {
  _ match {
    case P => ??? // x N
  }
}

// После
seq.map {
  case P => ??? // x N
}

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

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

Конвертируйте flatMap с частичной функцией collect

// До
seq.flatMap {
  case P => Seq(???) // x N
  case _ => Seq.empty
}

// После
seq.collect {
  case P => ??? // x N
}

Обновленное выражение дает аналогичный результат и выглядит намного проще.
Также применимо к: Set, Option, Map, Iterator.

Преобразовать match к collect, когда результатом является коллекция

// До
v match {
  case P => Seq(???) // x N
  case _ => Seq.empty
}

// После
Seq(v) collect {
  case P => ??? // x N
}

Учитывая, что все case-операторы создают коллекции, можно упростить выражение, заменив match на вызов collect. Так мы создаем коллекцию всего один раз, опустив при этом явные ветки case для дефолтных случаев.
Лично я обычно использую этот трюк с Option, а не с последовательностями как таковыми.
Также применимо к: Set, Option, Iterator.

Не эмулируйте collectFirst

// До
seq.collect{case P => ???}.headOption

// После
seq.collectFirst{case P => ???}

Для такого случая у нас есть особый метод, который работает быстрее для неленивых коллекций.

  • Частичная функция должна быть чистой.
  • Также применимо к: Set, Map, Iterator.

4.10 Перерабатываем

Соединяем последовательные вызовы filter

// До
seq.filter(p1).filter(p2)

// После
seq.filter(x => p1(x) && p2(x))

Так мы можем избежать создания промежуточной коллекции (после первого вызова filter), чем облегчим участь сборщика мусора.
Мы так же можем использовать обобщенный подход, который полагается на представления (смотрите ниже), получив: seq.view.filter(p1).filter(p2).force.

  • Предикаты p1 и p2 должны быть чистыми функциями.
  • Также применимо к: Set, Option, Map, Iterator.

Соединяем последовательные вызовы map

// До
seq.map(f).map(g)

// После
seq.map(f.andThen(g))

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

Мы так же можем применить обобщенный подход, который полагается на view (смотрите ниже), получив: seq.view.map(f).map(g).force.

  • Функции f и g должны быть чистыми.
  • Также применимо к: Set, Option, Map, Iterator.

Сортируйте после фильтрации

// До
seq.sorted.filter(p)

// После
seq.filter(p).sorted

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

  • Подобное применимо ко всем возможным методам сортировки, таким как sortWith и sortBy.
  • Предикат p должен быть чистой функцией.

Не переворачивайте коллекцию явно перед вызовом map

// До
seq.reverse.map(f)

// После
seq.reverseMap(f)

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

Не переворачивайте коллекцию явно для получения обратного итератора

// До
seq.reverse.iterator

// После
seq.reverseIterator

К тому же последнее выражение проще и может быть более эффективным.

Не конвертируйте коллекцию Set для нахождения отдельных элементов

// До
seq.toSet.toSeq

// После
seq.distinct

Нет нужды создавать временное множество (во всяком случае явно), чтобы найти отдельные элементы.

Не эмулируйте slice

// До
seq.drop(x).take(y)

// После
seq.slice(x, x + y)

Для линейных последовательностей, ничего кроме ясно выраженных мыслей и намерений мы не получим. Однако, в случае с индексированными последовательностями мы можем ожидать потенциальный прирост производительности.
Также применимо к: Set, Map, Iterator.

Не эмулируйте splitAt

// До
val seq1 = seq.take(n)
val seq2 = seq.drop(n)

// После
val (seq1, seq2) = seq.splitAt(n)

Для линейных последовательностей (как для List, так и для Stream), упрощенные выражения будут выполняться быстрее из-за того, что результаты вычисляются за один проход.
Также применимо к: Set, Map.

Не эмулируйте span

// До
val seq1 = seq.takeWhile(p)
val seq2 = seq.dropWhile(p)

// После
val (seq1, seq2) = seq.span(p)

А так мы можем пройти последовательность и проверить предикат не два, а всего один раз.

  • Предикат p не должен иметь побочных эффектов.
  • Также применимо к: Set, Map, Iterator.

Не эмулируйте partition

// До
val seq1 = seq.filter(p)
val seq2 = seq.filterNot(p)

// После
val (seq1, seq2) = seq.partition(p)

Опять-таки, преимуществом будет вычисление в один проход

  • Предикат p не должен иметь побочных эффектов.
  • Также применимо к: Set, Map, Iterator.

Не эмулируйте takeRight

// До
seq.reverse.take(n).reverse

// После
seq.takeRight(n)

Последнее выражение более выразительно и потенциально более эффективно (как для индексированных, так и для линейных последовательностей).

Не эмулируйте flatten

// До (seq: Seq[Seq[T]])
seq.reduce(_ ++ _)
seq.fold(Seq.empty)(_ ++ _)
seq.flatMap(identity)

// После
seq.flatten

Нет необходимости делать это вручную: у нас уже есть встроенный метод.
Также применимо к: Set, Option, Iterator.

Не эмулируйте flatMap

// До (f: A => Seq[B])
seq.map(f).flatten

// После
seq.flatMap(f)

Опять-таки незачем писать велосипед. Улучшится не только выразительность, дополнительная коллекция создаваться тоже не будет.
Также применимо к: Set, Option, Iterator.

Не используйте map если результат игнорируется

// До
seq.map(???) // результат игнорируется

// После
seq.foreach(???)

Когда вам нужны именно побочные эффекты, оправданий вызову map нет. Такой вызов вводит в заблуждение, при том еще и менее эффективен.
Также применимо к: Set, Option, Map, Iterator.

Не используйте unzip для извлечения единственного элемента

// До (seq: Seq[(A, B]])
seq.unzip._1

// После
seq.map(_._1)

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

  • Другой возможный метод: unzip3.
  • Также применимо к: Set, Option, Map, Iterator.

Не создавайте временные коллекции

Этот рецепт разбит на три части (в зависимости от конечного результата преобразования).

1) Преобразование сокращает коллекцию до единственного значения.

// До
seq.map(f).flatMap(g).filter(p).reduce(???)

// После
seq.view.map(f).flatMap(g).filter(p).reduce(???)

Вместо reduce может быть любой метод, который сокращает коллекцию до единственного значения, например: reduceLeft, reduceRight, fold, foldLeft, foldRight, sum, product, min, max, head, headOption, last, lastOption, indexOf, lastIndexOf, find, contains, exists, count, length, mkString, и т.д.

Точный порядок преобразований не столь важен — важно то, что мы создаем одну, а то и несколько промежуточных коллекций не очень-то и нужных, при этом они будут занимать место в куче и нагружать GC. Это происходит потому, что по умолчанию все преобразователи коллекций (map, flatMap, filter, ++, и т.д.) являются «строгими» (за исключениемStream) и, как результат, порождают новую коллекцию со всеми ее элементами.

Здесь на помощь приходят представления (view) — о которых вы можете думать, как о своего рода итераторах, позволяющих повторную итерацию:

  • Представления "ленивы" — элементы создаются только когда необходимы.
  • Представления не содержат созданных элементов в памяти (чем грешат даже Stream).

Чтобы перейти от коллекции к ее представлению, используйте метод view.

2) Преобразование, порождающее коллекцию того же типа.

Представления можно использовать и тогда, когда конечный результат преобразования по-прежнему остается коллекцией — метод force построит коллекцию первоначального типа (при этом все промежуточные коллекции созданы не будут):

// До
seq.map(f).flatMap(g).filter(p)

// После
seq.view.map(f).flatMap(g).filter(p).force

Если фильтрация — единственное промежуточное преобразование, то, как вариант, вы можете рассмотреть метод withFilter:

seq.withFilter(p).map(f)

Первоначально этот метод предназначался для использования внутри "for comprehensions". Он работает так же, как и представление — создает временный объект, который ограничивает область последующих преобразований коллекции (так, что он реорганизует возможные побочные эффекты). Однако, нет нужды явно преобразовывать коллекцию к (или наоборот) от временного представления (вызвав veiw и force)

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

3) Преобразование порождает коллекцию другого типа.

// До
seq.map(f).flatMap(g).filter(p).toList

// После
seq.view.map(f).flatMap(g).filter(p).toList

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

Также существует альтернативный способ совладать с «преобразованием + конверсией». И случай этот полагается на breakOut:

seq.map(f)(collection.breakOut): List[T]

Функционально выражение эквивалентно использованию представления, однако:

  • требует явного указания ожидаемого типа (что, зачастую, требует дополнительного указания типа),
  • ограничивается единичным преобразованием (как, например, map, flatMap, filter, fold, и т.д.),
  • выглядит весьма заумно (в виду того, что неявные билдеры обычно опускают из документации стандартной библиотеки коллекций Scala).

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

Представления наиболее целесообразны при относительно большом размере коллекций.

  • Все перечисленные функции (как f и g) и предикаты (p) должны быть чистыми функциями (так как представление может задерживать, пропускать, а то и вовсе переупорядочивать вычисления).
  • Также применимо к: Set, Map.

Используйте операторы для переприсванивания последовательностей

// До
seq = seq :+ x
seq = x +: seq
seq1 = seq1 ++ seq2
seq1 = seq2 ++ seq1

// После
seq :+= x
seq +:= x
seq1 ++= seq2
seq1 ++:= seq2

Scala предлагает «синтаксический сахар», известный как «операторы присваивания» (“assignment operators”) — он автоматически приводит операторы типа x <op>= y к виду x = x <op> y, где: <op> некий символьный оператор (например: +, -, и т.д). Обратите внимание, что если <op> заканчивается на :, то он считается право-ассоциативным (т.е. вызывается для правого выражения, вместо левого). Для списков и стримов также существует особый синтаксис:

// До
list = x :: list
list1 = list2 ::: list

stream = x #:: list
stream1 = stream2 #::: stream

// После
list ::= x
list1 :::= list2

stream #::= x
stream1 #:::= stream2

Упрощенные выражения лаконичны.
Также применимо к Set, Map, Iterator (учитывая специфику операторов).

Не приводите коллекции к заданному типу вручную

// До
seq.foldLeft(Set.empty)(_ + _)
seq.foldRight(List.empty)(_ :: _)

// После
seq.toSet
seq.toList

Для этого существуют встроенные методы, которые и чище, и быстрее. А если вам нужно преобразовать или отфильтровать значения во время преобразования, рассмотрите использование представлений или схожих техник, описанных выше.
Также применимо к: Set, Option, Iterator.

Берегитесь toSeq для нестрогих коллекций.

// До (seq: TraversableOnce[T])
seq.toSeq

// После
seq.toStream
seq.toVector

Из-за того, что Seq(...) создает строгую коллекцию (а именно, Vector), мы можем захотеть использовать toSeq для преобразования нестрогой сущности (как Stream, Iterator или view) к строгой коллекции. Однако TraversableOnce.toSeq на самом деле возвращает Stream, являющийся ленивой коллекцией, что может привести к труднонаходимым багам и проблемам с производительностью. Даже если вы изначально ожидали стрим, подобное выражение может ввести в заблуждение тех, кто читает ваш код.

А вот и типичный пример ловушки:

val source = Source.fromFile("lines.txt")
val lines = source.getLines.toSeq
source.close()
lines.foreach(println)

Такой код выбросит IOException, сетующий на то, что стрим уже закрыт.

Чтобы ясно обозначить наши намерения, лучше добавить toStream явно или, если нам после всего потребуется строгая коллекция, использовать toVector вместо toSeq.

Не приводите к строковому типу вручную

// До (seq: Seq[String])
seq.reduce(_ + _)
seq.reduce(_ + separator + _)
seq.fold(prefix)(_ + _)
seq.map(_.toString).reduce(_ + _) // seq: Seq[T]
seq.foldLeft(new StringBuilder())(_ append _)

// После
seq.mkString
seq.mkString(prefix, separator, "")

Последний подход чище и потенциально быстрее, так как внутри он использует единственный StringBuilder.

  • Другие возможные методы: reduceLeft, reduceRight, foldLeft, foldRight.
  • Также применимо к: Set, Option, Iterator.

5. Множесва (Sets)

Большинство советов для последовательностей так же хорошо работают и для множеств. Более того, для множеств есть несколько специфичных советов.

Не используйте sameElements для сравнения неупорядоченных коллекций

// До
set1.sameElements(set2)

// После
set1 == set2

Ранее мы уже ознакомились с этим правилом (на примере последовательностей), однако для множеств обоснование будет наиболее логичным.

Метод sameElements может возвращать недетерминированные результаты для неупорядоченных коллекций, потому что этот метод принимает во внимание порядок элементов, на который мы не можем полагаться в случае с множествами.
Исключениями из правила будут классы, которые явно гарантируют предсказуемый порядок итерации: например, LinkedHashSet.
Также применимо к: Map.

Используйте экземпляр Set как объект-функцию

// До (set: Set[Int])
Seq(1, 2, 3).filter(set(_))
Seq(1, 2, 3).filter(set.contains)

// После
Seq(1, 2, 3).filter(set)

Так как Set[T] также явялется экземпляром Function1[T, Boolean], вы можете использовать его в этом качестве.

Не вычисляйте пересечения множеств вручную

// До
set1.filter(set2.contains)
set1.filter(set2)

// После
set1.intersect(set2) // или set1 & set2

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

Не вычисляйте разницу множеств вручную

// До
set1.filterNot(set2.contains)
set1.filterNot(set2)

// После
set1.diff(set2) // или set1 &~ set2

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

6. Options

Технически Option не является частью Scala коллекций, однако предоставляет похожий интерфейс (с монадическими методами и т.д.) и даже ведет себя как специальный тип коллекций, который может иметь, а может и не иметь какое-то значение.

Многие из приведенных советов для последовательностей применимы и к Option. Кроме того, здесь представлены советы, характерные для Option API.

6.1 Значение

Не сравнивайте значения Option с None

// До
option == None
option != None

// После
option.isEmpty
option.isDefined

При том, что сравнение является вполне законным, есть более простой способ, который позволяет проверить объявлен ли Option.
Еще одно преимущество данного упрощения в том, что если вы решите изменить тип от Option[T] к T, scalac скомпилирует предшествующее выражение (выдав только одно предупреждение), тогда как компиляция последнего справедливо закончится ошибкой.

Не сравнивайте значения Option с Some

// До
option == Some(v)
option != Some(v)

// После
option.contains(v)
!option.contains(v)

Этот совет дополняет предыдущий.

Не полагайтесь isInstanceOf для проверки наличия элемента

// До
option.isInstanceOf[Some[_]]

// После
option.isDefined

В подобном трюкачестве нет нужды.

Не прибегайте к сопоставлению с образцом для проверки существования

// До
option match {
  case Some(_) => true
  case None => false
}

option match {
  case Some(_) => false
  case None => true
}

// После
option.isDefined
option.isEmpty

Опять же, первое выражение и является корректным — оправдывать подобную экстравагантность не стоит. Более того, упрощенное выражение будет работать быстрее.
Также применимо к: Seq, Set.

Не отрицайте значения свойств, связанных с существованием

// До
!option.isEmpty
!option.isDefined
!option.nonEmpty

// После
seq.isDefined
seq.isEmpty
seq.isEmpty

Причина та же, что и для последовательностей — простое свойство добавит меньше визуального шума, нежели составное выражение.
Заметьте, что у нас есть синонимы: isDefined (специфичный для option) и nonEmpty (специфичный для последовательностей). Возможно, было бы разумно отдать предпочтение первому для явного отделения Option и последовательностей.

6.2 Null

Не выполняйте явное сравнение значений с null, чтобы создать Option

// До
if (v != null) Some(v) else None

// После
Option(v)

Для этого у нас есть более подходящий синтаксис.

Не предоставляйте null как явную альтернативу

// До
option.getOrElse(null)

// После
option.orNull

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

6.3 Обработка

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

В документации, посвященной интерфейсу Option, говорится, что «самый идиоматичный способ использования экземпляра Option — это рассмотрение его в качестве коллекции или монады на ряду с использованием map, flatMap, filter или foreach». Основной принцип здесь заключается в том, чтобы избегать "check & get" (проверь и возьми) цепочек, которые обычно реализуются через оператор if или сопоставлением с образцом.
Цель — надежность, выразительность и «монадический» код:

  • более выразительный и понятный,
  • защищенный от NoSuchElementException и MatchError ислючений во время выполнения

Это объяснение объединяет все последующие случаи.

Не эмулируйте getOrElse

// До
if (option.isDefined) option.get else z

option match {
  case Some(it) => it
  case None => z
}

// После
option.getOrElse(z)

Не эмулируйте orElse

// До
if (option1.isDefined) option1 else option2

option1 match {
  case Some(it) => Some(it)
  case None => option2
}

// После
option1.orElse(option2)

Не эмулируйте exists

// До
option.isDefined && p(option.get)

if (option.isDefined) p(option.get) else false

option match {
  case Some(it) => p(it)
  case None => false
}

// После
option.exists(p)

Не эмулируйте forall

// До
option.isEmpty || (option.isDefined && p(option.get))

if (option.isDefined) p(option.get) else true

option match {
  case Some(it) => p(it)
  case None => true
}

// После
option.forall(p)

Не эмулируйте contains

// До
option.isDefined && option.get == x

if (option.isDefined) option.get == x else false

option match {
  case Some(it) => it == x
  case None => false
}

// После
option.contains(x)

Не эмулируйте foreach

// До
if (option.isDefined) f(option.get)

option match {
  case Some(it) => f(it)
  case None =>
}

// После
option.foreach(f)

Не эмулируйте filter

// До
if (option.isDefined && p(option.get)) option else None

option match {
  case Some(it) && p(it) => Some(it)
  case _ => None
}

// После
option.filter(p)

Не эмулируйте map

// До
if (option.isDefined) Some(f(option.get)) else None

option match {
  case Some(it) => Some(f(it))
  case None => None
}

// После
option.map(f)

Не эмулируйте flatMap

// До (f: A => Option[B])
if (option.isDefined) f(option.get) else None

option match {
  case Some(it) => f(it)
  case None => None
}

// После
option.flatMap(f)

6.4 Перерабатываем

Приводим цепочку из map и getOrElse в fold

// До
option.map(f).getOrElse(z)

// После
option.fold(z)(f)

Приведенные выражения семантически эквиваленты (в обоих случаях z будет вычислен лениво — по требованию), однако последнее выражение короче. Преобразование может требовать дополнительного указания типа (из-за особенностей работы вывода типов в Scala), и в таких случаях предыдущее выражение предпочтительнее.

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

Не эмулируйте exists

// До
option.map(p).getOrElse(false)

// После
option.exists(p)

Мы представили довольно похожее правило для последовательностей (которое применимо и к Option). Нетипичное преобразование для вызова getOrElse.

Не эмулируйте flatten

// До (option: Option[Option[T]])
option.map(_.get)
option.getOrElse(None)

// После
option.flatten

Последнее выражение смотрится чище.

Не конвертируйте Option в Seq вручную

// До
option.map(Seq(_)).getOrElse(Seq.empty)
option.getOrElse(Seq.empty) // option: Option[Seq[T]]

// После
option.toSeq

Для этого есть специальный метод, который делает это кратко и наименее затратно.

7. Таблицы

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

Не выполняйте поиск значений вручную

// До
map.find(_._1 == k).map(_._2)

// После
map.get(k)

В принципе, первый фрагмент кода будет работать, однако производительность будет неоптимальной из-за того, что Map не является простой коллекцией пар (ключ, значение) — она может выполнять поиск куда более эффективным способом. Более того, последнее выражение проще и легче для понимания.

Не используйте get, когда необходимо сырое значение

// Before
map.get(k).get

// After
map(k)

Нет необходимости плодить промежуточный Option, когда необходимо сырое (raw) значение.

Не используйте lift вместо get

// Before
map.lift(k)

// After
map.get(k)

Незачем рассматривать значение таблицы, как частичную функцию для получения опционального результата (что полезно для последовательностей), потому что у нас есть встроенный метод с такой же функциональностью. Хотя lift отлично работает, он выполняет дополнительное преобразование (от Map доPartialFunction) и может выглядеть весьма запутанным.

Не вызывайте get и getOrElse раздельно

// До
map.get(k).getOrElse(z)

// После
map.getOrElse(k, z)

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

Используйте экземпляр Map в качестве объекта-функции

// До (map: Map[Int, T])
Seq(1, 2, 3).map(map(_))

// После
Seq(1, 2, 3).map(map)

Так как экземпляр Map[K, V] также является Function1[K, V], вы можете использовать его как функцию.

Не извлекайте ключи вручную

// До
map.map(_._1)
map.map(_._1).toSet
map.map(_._1).toIterator

// После
map.keys
map.keySet
map.keysIterator

Оптимизированные выражения являются более понятными (и потенциально более быстрыми).

Не извлекайте значения вручную

// До
map.map(_._2)
map.map(_._2).toIterator

// После
map.values
map.valuesIterator

Упрощенные выражения понятней (и потенциально быстрее).

Будьте осторожны с filterKeys

// До
map.filterKeys(p)

// После
map.filter(p(_._1))

Метод filterKeys обертывает исходную таблицу без копирования каких-либо элементов. В этом нет ничего плохого, однако вы вряд ли ожидаете от filterKeys подобного поведения. Поскольку оно неожиданно ведет так же, как представление, производительность кода может быть существенно снижена для некоторых случаев, например, для filterKeys(p).groupBy(???).

Другой вероятной неприятностью является неожиданная «ленивость» (по умолчанию, фильтры коллекций должны быть строгими) – при вызове самого метода предикат вообще не вычисляется, из-за чего возможные побочные эффекты могут быть переупорядочены.

Метод filterKeys, скорее всего, следовало бы объявить устаревшим, из-за невозможности сделать его строгим, не сломав обратную совместимость. Более подходящим именем для текущей реализации будет withKeyFilter (по аналогии с withFilter).

В общем, наиболее разумно будет следовать Правилу наименьшего удивления и фильтровать ключи вручную.

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

Для того, чтобы не вводить в заблуждение людей, читающих (или модифицирующих) наш код, лучшим решением будет подчеркнуть наши намерения, объявив подходящий синоним:

type MapView[A, +B] = Map[A, B]

implicit class MapExt[A, +B](val map: Map[A, B]) extends AnyVal {
  def withKeyFilter(p: A => Boolean): MapView[A, B] =
    map.filterKeys(p)
}

Мы используем псевдоним типа MapView для того, чтобы обозначить, что результирующая таблица является view-подобной. Другим вариантом будет объявление простого вспомогательного метода:

def get(k: T) = if (p(k)) map.get(k) else None

Будьте осторожны с mapValues

// До
map.mapValues(f)

// После
map.map(f(_._2))

Обоснование такое же, как и в предыдущем случае. Аналогичным способом мы можем объявить недвусмысленный синоним:

type MapView[A, +B] = Map[A, B]

implicit class MapExt[A, +B](val map: Map[A, B]) extends AnyVal {
  def withValueMapper[C](f: B => C): MapView[A, C] =
    map.mapValues(f)
}

Проще объявить вспомогательный метод вроде:

def get(k: T) = map.get(k).map(f)

Не отфильтровывайте ключи вручную

// До
map.filterKeys(!seq.contains(_))

// После
map -- seq

Мы можем полагаться на упрощенный синтаксис, чтобы отфильтровать ключи.

Используйте операторы переприсваивания таблиц

// До
map = map + x -> y
map1 = map1 ++ map2
map = map - x
map = map -- seq

// После
map += x -> y
map1 ++= map2
map -= x
map --= seq

Также, как и с последовательностями, мы можем полагаться на синтаксический сахар для упрощения подобных операторов.

8. Дополнение

В дополнение к приведенным рецептам я рекомендую вам посмотреть на официальную документацию библиотеки коллекций Scala, которую на удивление легко читать.

Смотрите также:

  • Scala for Project Euler — Выразительные функциональные решения проблем проекта Эйлер на Scala.
  • Ninety-nine — Девяносто девять проблем на Scala, Java, Clojure и Haskell (с множеством решений).

Эти головоломки оказали мне неоценимую помощь в формировании и углублении понимания коллекций Scala.

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

От переводчика

Большое спасибо Павлу Фатину за разрешение на перевод статьи. Спасибо Ледовских Владу за вычитку перевода (этот абзац никто не вычитывал). Благодарю firegurafiku за ценные советы и рекомендации, которые помогли мне в переводе.

Автор: Павел Попов

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js