 | Библиотека коллекции в scala - одна из самых сильных особенностей языка, но в то же время и одна самых трудных его частей. Данная статья представляет собой конспект особенностей и нюансов коллекций в scala. Содержание:
|
Обзор
|
 |
| Интерфейсы коллекций в 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().asJavaIterator <=> 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)Теперь, когда вы знаем о том, что коллекции в scala не всегда бывают конечными, вас не должен удивить метод hasDefiniteSize, возвращающий true, если коллекция конечного размера.
Ленивые коллекции View
def solution(numbers: Seq[Int]): Seq[Int] = numbers filter (_ < 0) map (x => x * x)Да, это действительно так. В результате фильтрации будет создана новая коллекция, копирующая(в общем случае) отрицательные элементы из предыдущей. И после выполнения операции map клонирование коллекции повторится. Таким образом, чем больше операций в цепочке, тем сильнее потери в производительности!
Но не спешите кидать камни в, местами заслуживающую это, Scala. Приберегите их для свойств объектов :)
Специально для таких цепочек преобразований в scala предусмотрены ленивые коллекции называемые View. Это что-то вроде виртуальных коллекций, которые не содержат элементов, а лишь ссылаются на оригинальную коллекцию. Суть их очень проста, вместо создания новой коллекции после каждой операции, они применяют сразу всю цепочку преобразований к каждому элементу оригинальной коллекции, благодаря чему цепочка преобразований выполняется за один проход. Для преобразования оригинальной коллекции во view есть соответствующий метод view:
def solution(numbers: Seq[Int]): Seq[Int] = numbers.view filter (_ < 0) map (x => x * x)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)
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, 4scala> 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)
Производительность коллекций
Обозначения
| c | Операция выполняет за постоянное время. |
| ~c | Операция занимает эффективное постоянное время, но может зависеть от некоторых условий, таких как длинна коллекции или распределение хеш-ключей. |
| c* | Операция занимает в общем случае константное время, но некоторые вызовы могут выполняться дольше. |
| log n | Время выполнения операции пропорционально логарифму от размера коллекции. |
| n | Линейная операция, время выполнения которой пропорционально размеру коллекции. |
| - | Операция не поддерживается. |
Последовательности
| head | tail | apply | update | prepend | append | insert | |
|---|---|---|---|---|---|---|---|
| immutable | |||||||
List | c | c | n | n | c | n | - |
Stream | c | c | n | n | c | n | - |
Vector | ~c | ~c | ~c | ~c | ~c | ~c | - |
Stack | c | c | n | n | c | c | n |
Queue | c* | c* | n | n | n | c | - |
Range | c | c | c | - | - | - | - |
String | c | n | c | n | n | n | - |
| mutable | |||||||
ArrayBuffer | c | n | c | c | n | c* | n |
ListBuffer | c | n | n | n | c | c | n |
StringBuilder | c | n | c | c | n | c* | n |
MutableList | c | n | n | n | c | c | n |
Queue | c | n | n | n | c | c | n |
ArraySeq | c | n | c | c | - | - | - |
Stack | c | n | n | n | c | n | n |
ArrayStack | c | n | c | c | c* | n | n |
Array | c | n | c | c | - | - | - |
Множества и ассоциативные массивы
| lookup | add | remove | min | |
|---|---|---|---|---|
| immutable | ||||
HashSet/HashMap | ~c | ~c | ~c | n |
TreeSet/TreeMap | log n | log n | log n | log n |
BitSet | c | n | n | ~c |
ListMap | n | n | n | n |
| mutable | ||||
HashSet/HashMap | ~c | ~c | ~c | n |
WeakHashMap | ~c | ~c | ~c | n |
BitSet | c | c* | c | ~c |
TreeSet | log n | log n | log n | log n |
Конспект по методам коллекций
Коллекции в scala имеют огромный список методов для выполнения всевозможных операций как над самими коллекциями, так и над элементами. Лучшим источником информации о всевозможных методах безусловно является документация. Но проблема в том, что методов слишком много и не понятно с чего начать. Вот как раз начать, я советую со статьи из цикла Scala school от twiter, посвященной функциональным комбинаторам. Она содержит описание самых распространенных операций. Еще одним хорошим сводным источником информации могу рекомендовать 13 главу из книги Scala для нетерпеливых. Здесь я позволю себе привести сводную таблицу по методам из этой книги:
 |
 |
Замечание к вопросу Scala collections vs Java streams
Стремление авторов библиотеки коллекций в Scala понятно - желание быть последовательными в дизайне и дать разработчикам гибкий и удобный инструмент для преобразования коллекций. Но на мой взгляд цена такого решения слишком высока. Простота вызова функциональных комбинаторов может посеять множество трудно уловимых потерь в производительности. Любой их вызов должен быть тщательно продуман и взвешен.
В то же время, решение введения новой сущности в лице Streams в Java хоть и вносит некоторую избыточность и отстает по гибкости и функциональности от аналогов в scala, все-таки позволяет избежать случайного падения производительности, что в условиях работы в больших коллективах и с большой кодовой базой является серьезным преимуществом.
Заключение
Коллекции в scala - крайне мощный инструмент в руках внимательного разработчика. Сложность и обилие методов требует некоторого времени на их понимание и наработку навыков применения, но польза от потраченного времени не заставит себя ждать. Главное не поддаваться на кажущуюся простоту коллекций и внимательно следить за тем, что вы делаете и к чему это приводит.
Комментариев нет:
Отправить комментарий