Что надо знать про коллекции в Scala

среда, 11 мая 2016 г.
Библиотека коллекции в scala - одна из самых сильных особенностей языка, но в то же время и одна самых трудных его частей. Данная статья представляет собой конспект особенностей и нюансов коллекций в scala.

Содержание:


Обзор


В scala коллекции делятся на изменяемые и неизменяемые, что положительно выделяет их на фоне стандартной библиотеки коллекций в Java.
Интерфейсы коллекций в scala.collection Интерфейсы коллекций в Java

Неизменяемые коллекции

Неизменяемые коллекции находятся в пакете scala.collection.immutable. Коллекции в данном пакете не реализуют методов изменяющих их внутреннее состояние, вместо этого все методы, добавляющие элементы, удаляющие их  или иначе изменяющие коллекцию, создают новый экземпляр оригинальной коллекции содержащий соответствующие изменения.
scala> List(1, 2) ++ List(3, 4)
res0: List[Int] = List(1, 2, 3, 4)

Неизменяемые коллекции в scala.collection.immutable

Изменяемые коллекции

Изменяемые коллекции находятся в пакете scala.collection.mutable и реализуют общие с неизменяемыми коллекциями интерфейсы из пакета scala.collection. Т.к. интерфейсы у mutable и immutable коллекций одни, все методы неизменяемых коллекций доступны и для изменяемых коллекций, но последние, в дополнение, содержат методы для изменения своего внутреннего состояния.
scala> val buffer = collection.mutable.Buffer(1,2,3)
buffer: scala.collection.mutable.Buffer[Int] = ArrayBuffer(1, 2, 3)

scala> buffer.append(4)

scala> buffer
res6: scala.collection.mutable.Buffer[Int] = ArrayBuffer(1, 2, 3, 4)

Изменяемые коллекции в scala.collection.mutable

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

Вместо этого отмечу, что в силу популярности коллекций, чтобы не импортировать нужные пакеты всякий раз, когда вам понадобится список, в scala предусмотрели псевдонимы для наиболее популярных коллекций прямо в пакете scala, который негласно импортируется всегда. Среди них: Traversable, Iterable, Seq, IndexedSeq, Iterator, Stream, Vector, List, StringBuilder и Range.

Java коллекции

Так как scala - язык работающий поверх JVM, ему доступно все богатство библиотек для Java, и коллекции здесь не исключение. Можно импортировать и создавать коллекции из пакета java.util точно также как и любые другие классы. Но java коллекции не реализуют интерфейсов scala коллекций, что может затруднить работу в случае необходимости передать scala-коллекцию в java-код или наоборот, java-коллекцию в scala функцию. К счастью в scala реализованы специальные конверторы, позволяющие неявно преобразовывать java-коллекции в их scala аналоги совершенно прозрачно. Для этого достаточно выполнить импорт объекта JavaConverters и всех его методов:
import collection.JavaConverters._

val buffer: mutable.Buffer[Int] = new java.util.ArrayList[Int]().asScala
val list: java.util.List[Int] = new mutable.ArrayBuffer().asJava
Таблица соответстия между коллекциями выглядит следующим образом:
Iterator               <=>     java.util.Iterator
Iterator               <=>     java.util.Enumeration
Iterable               <=>     java.lang.Iterable
Iterable               <=>     java.util.Collection
mutable.Buffer         <=>     java.util.List
mutable.Set            <=>     java.util.Set
mutable.Map            <=>     java.util.Map
mutable.ConcurrentMap  <=>     java.util.concurrent.ConcurrentMap

Преобразования коллекций

Для удобства использования, для каждой коллекции определены методы для преобразования в коллекцию другого типа вида to{Название коллекции}:
def toArray : Array[A]
def toArray [B >: A] (implicit arg0: ClassManifest[B]) : Array[B]
def toBuffer [B >: A] : Buffer[B]
def toIndexedSeq [B >: A] : IndexedSeq[B]
def toIterable : Iterable[A]
def toIterator : Iterator[A]
def toList : List[A]
def toMap [T, U] (implicit ev: <: :="" def="" map="" seq="" toseq="" toset="" u="">: A] : Set[B]
def toStream : Stream[A]
def toString () : String
def toTraversable : Traversable[A]

Streams


Среди прочих коллекций в scala, хочется отметить scala.collection.immutable.Stream. Это рекуррентно вычисляемая коллекция бесконечной длинны. Ее проще объяснить на примере, чем описывать словами. Типичным примером для демонстрации Stream в scala является задача вычисления N-го члена последовательности Фибоначи:
def fibFrom(a: Int, b: Int): Stream[Int] = a #:: fibFrom(b, a + b)
val fibs: Stream[Int] = fibFrom(1, 1).take(7)
fibs.toList // = List(1, 1, 2, 3, 5, 8, 13)
Здесь следует отметить важный нюанс: stream кеширует вычисленный ранее результат и возвращает значение из кэша вместо повторного вычисления.

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

Ленивые коллекции View


Рассмотрим следующую простую задачу: пусть у нас есть случайный набор целочисленных значений, наша задача найти среди них отрицательные и возвести в квадрат. Благодаря богатому набору методов, решить эту задачу не составит труда:
def solution(numbers: Seq[Int]): Seq[Int] = numbers filter (_ < 0) map (x => x * x)
Но у внимательного и ответственного разработчика должен возникнуть вопрос об эффективности подобного решения. Ведь каждый из методов map и filter порождает новую коллекцию?!

Да, это действительно так. В результате фильтрации будет создана новая коллекция, копирующая(в общем случае) отрицательные элементы из предыдущей. И после выполнения операции map клонирование коллекции повторится. Таким образом, чем больше операций в цепочке, тем сильнее потери в производительности!

Но не спешите кидать камни в, местами заслуживающую это, Scala. Приберегите их для свойств объектов :)

Специально для таких цепочек преобразований в scala предусмотрены ленивые коллекции называемые View. Это что-то вроде виртуальных коллекций, которые не содержат элементов, а лишь ссылаются на оригинальную коллекцию. Суть их очень проста, вместо создания новой коллекции после каждой операции, они применяют сразу всю цепочку преобразований к каждому элементу оригинальной коллекции, благодаря чему цепочка преобразований выполняется за один проход. Для преобразования оригинальной коллекции во view есть соответствующий метод view:
def solution(numbers: Seq[Int]): Seq[Int] = numbers.view filter (_ < 0) map (x => x * x)
Обратите внимание на то, что по факту такой метод возвращает не просто Seq, а именно SeqView. Т.е. инструкции по преобразованию оригинальной коллекции, а не готовый результат. Если в метод передать изменяемую коллекцию и затем изменить ее элементы, то это повлечет перемены и в результате работы метода:
scala> def solution(numbers: Seq[Int]) = numbers.view filter (_ < 0) map (x => x * x)
solution: (numbers: Seq[Int])scala.collection.SeqView[Int,Seq[_]]

scala> val arg = Array(-1, 2, -3)
arg: Array[Int] = Array(-1, 2, -3)

scala> val result = solution(arg)
result: scala.collection.SeqView[Int,Seq[_]] = SeqViewFM(...)

scala> result.toList
res8: List[Int] = List(1, 9)

scala> arg(0) = 4

scala> result.toList
res10: List[Int] = List(9)
Преобразование виртуальной коллекции в реальную выполняется либо одним из преобразующих методов из серии to{Название коллекции}, либо методом force:
scala> def solution(numbers: Seq[Int]) = numbers.view filter (_ < 0) map (x => x * x) force
solution: (numbers: Seq[Int])Seq[Int]

scala> val arg = Array(-1, 2, -3)
arg: Array[Int] = Array(-1, 2, -3)

scala> val result = solution(arg)
result: Seq[Int] = ArrayBuffer(1, 9)

scala> arg(0) = 4

scala> result.toList
res12: List[Int] = List(1, 9)

Ranges


Интервалы в scala - это упорядоченные последовательности целых чисел из заданного диапазона и изменяющихся с некоторым шагом:
new Range(0, 6, 2) // Создает диапазон чисел [0, 6) с шагом 2, т.е. 0, 2, 4
Диапазон чисел доступных для использования в Range соответствует диапазону типа Int. Для удобства использования, в классе RichInt определены методы to и until. Первый создает диапазон, включающий обе границы, второй - включает только первую границу диапазона. Оба метода возвращают Inclusive - наследника класса Range, несколько его расширяющего. В частности привносящего метод by, который позволяет указать шаг между значениями диапазона:
scala> 0 until 6
res0: scala.collection.immutable.Range = Range(0, 1, 2, 3, 4, 5)

scala> 0 to 6
res1: scala.collection.immutable.Range.Inclusive = Range(0, 1, 2, 3, 4, 5, 6)

scala> 0 to 6 by 2
res2: scala.collection.immutable.Range = Range(0, 2, 4, 6)
Реализация Range не содержит всех элементов диапазона, а хранит только его границы и шаг, что делает использование этих коллекций очень дешевым.


Производительность коллекций



Обозначения

cОперация выполняет за постоянное время.
~cОперация занимает эффективное постоянное время, но может зависеть от некоторых условий, таких как длинна коллекции или распределение хеш-ключей.
c*Операция занимает в общем случае константное время, но некоторые вызовы могут выполняться дольше. 
log nВремя выполнения операции пропорционально логарифму от размера коллекции.
nЛинейная операция, время выполнения которой пропорционально размеру коллекции.
-Операция не поддерживается.

Последовательности

headtailapplyupdateprependappendinsert
immutable
Listccnncn-
Streamccnncn-
Vector~c~c~c~c~c~c-
Stackccnnccn
Queuec*c*nnnc-
Rangeccc----
Stringcncnnn-
mutable
ArrayBuffercnccnc*n
ListBuffercnnnccn
StringBuildercnccnc*n
MutableListcnnnccn
Queuecnnnccn
ArraySeqcncc---
Stackcnnncnn
ArrayStackcnccc*nn
Arraycncc---

Множества и ассоциативные массивы

lookupaddremovemin
immutable
HashSet/HashMap~c~c~cn
TreeSet/TreeMaplog nlog nlog nlog n
BitSetcnn~c
ListMapnnnn
mutable
HashSet/HashMap~c~c~cn
WeakHashMap~c~c~cn
BitSetcc*c~c
TreeSetlog nlog nlog nlog n



Конспект по методам коллекций


Коллекции в scala имеют огромный список методов для выполнения всевозможных операций как над самими коллекциями, так и над элементами. Лучшим источником информации о всевозможных методах безусловно является документация. Но проблема в том, что методов слишком много и не понятно с чего начать. Вот как раз начать, я советую со статьи из цикла Scala school от twiter, посвященной функциональным комбинаторам. Она содержит описание самых распространенных операций. Еще одним хорошим сводным источником информации могу рекомендовать 13 главу из книги Scala для нетерпеливых. Здесь я позволю себе привести сводную таблицу по методам из этой книги:


Замечание к вопросу Scala collections vs Java streams


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

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


Заключение


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

0 коммент. :: Что надо знать про коллекции в Scala

Отправить комментарий

Ваше мнение мне искренне интересно. Смелее!

Технологии Blogger.