Отображения

У коллекций довольно много вариантов создания новых коллекций. Ну например используя операции map, filter или ++. Мы называем такие операции трансформерами, потому что они берут хотя бы одну коллекцию и трансформируют её в новую коллекцию.

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

В качестве примера не строгого трансформера рассмотрим следующую реализацию операции создания ленивой мапы:

def lazyMap[T, U](coll: Iterable[T], f: T => U) = new Iterable[U] {
  def iterator = coll.iterator map f
}

Обратите внимание, что lazyMap создает новую Iterable , не обходя все элементы коллекции coll. Функция f применяется к элементам новой коллекции iterator по мере запроса ее элементов.

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

Для перехода от коллекции к ее отображению можно использовать метод view (отобразить) у коллекции. Если xs - это какая-то коллекция, то xs.view - это та же самая коллекция, но со всеми трансформерами, реализованными лениво. Чтобы вернуться от такого отображения к строгой коллекции, можно использовать операцию преобразования to с указанием создаваемой коллекции в качестве параметра (например, xs.view.to(List)).

Давайте рассмотрим пример. Допустим, у вас есть целочисленный вектор, на котором вы хотите последовательно применить две функции:

scala> val v = Vector(1 to 10: _*)
v: scala.collection.immutable.Vector[Int] =
   Vector(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
scala> v map (_ + 1) map (_ * 2)
res5: scala.collection.immutable.Vector[Int] =
   Vector(4, 6, 8, 10, 12, 14, 16, 18, 20, 22)

В последней строчке выражение v map (_ + 1) создает новый вектор, который при втором вызове в map (_ * 2) превращается в третий вектор. Как правило, построение промежуточного результата от первого вызова мапы расточительно. В приведенном выше примере было бы быстрее составить единую мапу, состоящую из двух функций (_ + 1) и (_ * 2). Если у вас обе функции доступны в одном и том же выражении, вы можете объединить их вручную. Но довольно часто последовательные преобразования структуры данных выполняются в различных модулях программы. Слияние этих преобразований отрицательно скажется на модульности. Более универсальным способом избежать промежуточных результатов - это превратить вектор сначало в отображение, затем применить все преобразования к отображению и, наконец, преобразовать отображение в вектор:

scala> (v.view map (_ + 1) map (_ * 2)).to(Vector)
res12: scala.collection.immutable.Vector[Int] =
   Vector(4, 6, 8, 10, 12, 14, 16, 18, 20, 22)  

Давайте повторим последовательность этих операций, одну за другой:

scala> val vv = v.view
vv: scala.collection.IndexedSeqView[Int] = IndexedSeqView(<not computed>)

Применение v.view дает нам IndexedSeqView[Int], тоесть лениво вычисляемым IndexedSeq[Int]. Так же как и LazyList, метод toString на отображении не принуждает выводить элементы, вот почему содержимое vv выводится как View(?).

Применение первого map к отображению дает:

scala> vv map (_ + 1)
res13: scala.collection.IndexedSeqView[Int] = IndexedSeqView(<not computed>)

Результатом работы map - еще один IndexedSeqView[Int]. По сути, это обёртка, которая записывает тот факт, что на вектор v необходимо наложить map с функцией (_ + 1). Однако эта мапа не будет применяться до тех пор, пока не будет принудительно запрошена. Теперь применим вторую map к последнему результату.

scala> res13 map (_ * 2)
res14: scala.collection.IndexedSeqView[Int] = IndexedSeqView(<not computed>)

Наконец, принудительно запросим результат:

scala> res14.to(Vector)
res15: scala.collection.immutable.Vector[Int] =
   Vector(4, 6, 8, 10, 12, 14, 16, 18, 20, 22)

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

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

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

Однако есть несколько исключений из этих правил. Например, операция sorted не может удовлетворять сразу оба свойства. В действительности, необходимо обойти всю основную коллекцию, чтобы найти ее минимальный элемент. С одной стороны, если этот обход произошел во время вызова sorted, то первое свойство будет нарушено (sorted не будет лениво отображен), с другой стороны, если обход произошел во время доступа к полученным элементам отображения, то второе свойство будет нарушено. Для таких операций мы решили нарушить первое свойство. Такие операции задокументированны как “всегда принуждающие к сбору всех элементов”.

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

def isPalindrome(x: String) = x == x.reverse
def findPalindrome(s: Seq[String]) = s find isPalindrome

Теперь предположим, что у вас очень длинная последовательность слов и вы хотите найти палиндром в первых миллионах слов этой последовательности. Можете ли вы повторно переиспользовать findPalindrome? Конечно, вы можете написать:

findPalindrome(words take 1000000)

Что прекрасно разделяет два аспекта: взятие первого миллиона слов последовательности и нахождение в ней палиндрома. Недостатком является то, что создается промежуточная последовательность, состоящая из одного миллиона слов, даже если первое слово из этой последовательности уже является палиндромным. Таким образом, возможно, 999’999 слов будут скопированы в промежуточный результат без последующей обработки. Многие программисты сдались бы здесь и написали бы свою собственную специализированную версию поиска палиндромов из заданного префикса последовательности аргументов. Но теперь с отображением, это не требуется делать. Достаточно написать:

findPalindrome(words.view take 1000000)

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

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

Приведу пример, который вызывал боль у пользователей Scala до версии 2.8. В прежних версиях тип Range был ленивым, он вел себя также как отображение. Люди пытались создать ряд сущностей (actors) как в примере:

val actors = for (i <- 1 to 10) yield actor { ... }

Они были озадачены тем, что ни один из actors не исполнялся, хотя их метод должен был создавать и запускать actor из кода, заключенного в фигурные скобки идущие следом. Чтобы объяснить, почему ничего не происходило, напомним, что выражению выше равнозначно применению мапы:

val actors = (1 to 10) map (i => actor { ... })

Так как диапазон, созданный с помощью (1 to 10), вел себя как отображение, результат мапы снова был отображением. То есть элемент не вычислялся, а значит actor не создавался! Они могли бы быть созданы путем принудительного вычисления всего диапазона, но это было не таким уж и очевидным решением.

Чтобы избежать подобных сюрпризов, в текущей библиотеке коллекций Scala действуют более привычные правила. Все коллекции, кроме ленивых списков и отображений, строгие. Единственный способ перейти от строгой коллекции к ленивой - метод view. Единственный способ вернуться обратно - использовать to. Таким образом, приведенное в примере объявление actors теперь будет вести себя так, как ожидалось, создавая и запуская 10 actors. Чтобы вернуть прежнее неочевидное поведение, необходимо добавить явный вызов метода view:

val actors = for (i <- (1 to 10).view) yield actor { ... }

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