Scala. Профессиональное программирование 2022. Одерски Мартин, Спун Лекс, Веннерс Билл, Соммерс ФрэнкО41 Scala. Профессиональное программирование. 5е изд спб. Питер, 2022. 608 с. ил. Серия Библиотека программиста
 Скачать 6.24 Mb.
|
|
539 конечными, и скоростью выполнения различных операций. Начнем с обзора наиболее востребованных типов неизменяемых коллекций. Списки Списки относятся к конечным неизменяемым последовательностям. Они обеспечивают постоянное время доступа к своим первым элементам, а также ко всей остальной части списка и имеют постоянное время выполнения опе раций cons для добавления нового элемента в начало списка. Многие другие операции имеют линейную зависимость времени выполнения от длины списка. Более подробно списки рассматриваются в главах 14 и 1. Ленивые списки Ленивые списки похожи на списки, за исключением того, что их элементы вычисляются лениво (или отложенно). Вычисляться будут только запрошен ные элементы. Поэтому ленивые списки могут быть бесконечно длинными. Во всем остальном они имеют такие же характеристики производительности, что и списки. В то время как списки конструируются с помощью оператора :: , ленивые конструируются с помощью похожего оператора #:: . Пример ленивого спи ска, содержащего целые числа 1 , 2 и 3 , выглядит следующим образом: scala> val str = 1 #:: 2 #:: 3 #:: LazyList.empty val str: scala.collection.immutable.LazyList[Int] = LazyList( «Голова» этого ленивого списка — 1 , а «хвост» — 2 и 3 . Но никакие элементы здесь не выводятся, поскольку список еще не вычислен! Ленивые списки объявлены как вычисляющиеся лениво, и метод toString , вызванный в от ношении такого списка, заботится о том, чтобы не навязывать лишние вы числения. Далее показан более сложный пример. В нем вычисляется ленивый список, содержащий последовательность чисел Фибоначчи с заданными двумя числами. Каждый элемент последовательности Фибоначчи есть сумма двух предыдущих элементов в серии: scala> def fibFrom(a: Int, b: Int): LazyList[Int] = a #:: fibFrom(b, a + b) def fibFrom: (a: Int, b: Int)LazyList[Int] 540 Глава 24 • Углубленное изучение коллекций Эта функция кажется обманчиво простой. Понятно, что первый элемент последовательности — a , за ним стоит последовательность Фибоначчи, на чинающаяся с b , затем — элемент со значением a + b . Самое сложное здесь — вычислить данную последовательность, не вызвав бесконечную рекурсию. Если функция вместо #:: использует оператор :: , то каждый вызов функции будет приводить к еще одному вызову, что выльется в бесконечную рекур сию. Но, поскольку применяется оператор #:: , правая часть выражения не вычисляется до тех пор, пока не будет востребована. Вот как выглядят первые несколько элементов последовательности Фибо наччи, начинающейся с двух заданных чисел: scala> val fibs = fibFrom(1, 1).take(7) val fibs: scala.collection.immutable.LazyList[Int] = LazyList( scala> fibs.toList val res23: List[Int] = List(1, 1, 2, 3, 5, 8, 13) Неизменяемые ArraySeq Списки очень эффективны в алгоритмах, которые работают исключитель но с начальными элементами. Получение, добавление и удаление начала списка занимает постоянное время. А вот получение или изменения по следующих элементов — это операции линейного времени, зависящие от длины списка. В результате список может быть не самым оптимальным вариантом для алгоритмов, которые не ограничиваются обработкой на чальных элементов. Последовательный массив ( ArraySeq ) — это неизменяемая последователь ность на основе приватного массива, которая решает проблему неэффек тивного произвольного доступа в списках. Последовательные массивы позволяют получить любой элемент коллекции за постоянное время. Бла годаря этому вы можете не ограничиваться работой только с начальными элементами. Время получения элемента не зависит от его местоположения, и потому ArraySeq может оказаться эффективней списков в некоторых алгоритмах. С другой стороны, тип ArraySeq основан на Array , поэтому добавление эле ментов в начало занимает линейное время, а не постоянное, как в случае со списками. Более того, на всякое добавление или обновление одного элемента в ArraySeq уходит линейное время, поскольку при этом копируется весь внутренний массив. 24 .7 . Конкретные классы неизменяемых коллекций 541 Векторы List и ArraySeq — структуры данных, эффективные для одних вариантов ис пользования и неэффективные для других. Например, добавление элемента в начало List занимает постоянное время, а в ArraySeq — линейное. С другой стороны, индексированный доступ занимает постоянное время в ArraySeq и линейное в List Вектор обеспечивает хорошую производительность для всех своих операций. Доступ и обновление любых элементов вектора занимает «эффективно по стоянное время», как описано ниже. Эти операции выполняются медленнее, чем получение начала списка или чтение элементов в последовательном массиве, но время их выполнения остается постоянным. В результате алго ритмы, использующие векторы, не должны ограничиваться доступом или обновлением только к началу последовательности. Они могут обращаться к элементам и обновлять их в произвольном месте и поэтому могут быть гораздо более удобными в написании. Создаются и изменяются векторы точно так же, как и любые другие после довательности: val vec = scala.collection.immutable.Vector.empty val vec2 = vec :+ 1 :+ 2 // Vector(1, 2) val vec3 = 100 +: vec2 // Vector(100, 1, 2) vec3(0) // 100 Для представления векторов используются широкие неглубокие деревья. Каждый узел дерева содержит до 32 элементов вектора или до 32 других узлов дерева. Векторы, содержащие до 32 элементов, могут быть представ лены одним узлом. Векторы с количеством элементов до 32 · 32 = 1024 могут быть представлены в виде одного направления. Двух переходов от корня дерева к конечному элементу достаточно для векторов, имеющих до 2 15 эле ментов, трех — для векторов с 2 20 , четырех — для векторов с 2 25 элементов, а пяти — для векторов с количеством элементов до 2 30 . Следовательно, для всех векторов разумного размера выбор элемента требует до пяти обычных доступов к массиву. Именно это мы имели в виду, когда написали «эффек тивно постоянное время». Векторы неизменяемы, следовательно, внести в элемент вектора изменение на месте невозможно. Но метод updated позволяет создать новый вектор, отличающийся от заданного только одним элементом: val vec = Vector(1, 2, 3) vec.updated(2, 4) // Vector(1, 2, 4) vec // Vector(1, 2, 3) 542 Глава 24 • Углубленное изучение коллекций Последняя строка данного кода показывает, что вызов метода updated никак не повлиял на исходный вектор vec . Функциональное обновление векторов также занимает «эффективно постоянное время». Обновить элемент в се редине вектора можно с помощью копирования узла, содержащего элемент, и каждого указывающего на него узла, начиная с корня дерева. Это значит, функциональное обновление создает от одного до пяти узлов, каждый из которых содержит до 32 элементов или поддеревьев. Конечно, это гораздо затратнее обновления на месте в изменяемом массиве, но все же намного дешевле копирования всего вектора. Векторы сохраняют разумный баланс между быстрым произвольным досту пом и быстрыми произвольными функциональными обновлениями, поэтому в настоящий момент они представляют исходную реализацию неизменяемых индексированных последовательностей: collection.immutable.IndexedSeq(1, 2, 3) // Vector(1, 2, 3) Неизменяемые очереди В очередях используется принцип «первым пришел, первым вышел». Упро щенная реализация неизменяемых очередей рассматривалась в главе 18. Создать пустую неизменяемую очередь можно следующим образом: val empty = scala.collection.immutable.Queue[Int]() Добавить элемент в неизменяемую очередь можно с помощью метода enqueue : val has1 = empty.enqueue(1) // Queue(1) Чтобы добавить в очередь сразу несколько элементов, следует вызвать метод enqueueAll с коллекцией в качестве его аргументов: val has123 = has1.enqueueAll(List(2, 3)) // Queue(1, 2, 3) Чтобы удалить элемент из начала очереди, следует воспользоваться методом dequeue : scala> val (element, has23) = has123.dequeue val element: Int = 1 has23: scala.collection.immutable.Queue[Int] = Queue(2, 3) Обратите внимание: dequeue возвращает пару, состоящую из удаленного элемента и оставшейся части очереди. 24 .7 . Конкретные классы неизменяемых коллекций 543 Диапазоны Диапазон представляет собой упорядоченную последовательность целых чисел с одинаковым интервалом между ними. Например, 1, 2, 3 является диапазоном точно так же, как и 5, 8, 11, 14. Чтобы создать в Scala диапазон, следует воспользоваться предопределенными методами to и by . Рассмотрим несколько примеров: 1 to 3 // Range(1, 2, 3) 5 to 14 by 3 // Range(5, 8, 11, 14) Если нужно создать диапазон, исключая его верхний предел, то следует вместо метода to воспользоваться методомпомощником until : 1 until 3 // Range(1, 2) Диапазоны представлены постоянным объемом памяти, поскольку могут быть определены всего тремя числами: их началом, их концом и значением шага. Благодаря такому представлению большинство операций над диапа зонами выполняется очень быстро. Сжатые коллекции HAMT Хешизвлечения (hashtries 1 ) — стандартный способ эффективной реали зации неизменяемых множеств и отображений. Сжатые коллекции HAMT (хешмассивы сопоставленных префиксных деревьев) 2 — разновидность хешизвлечений в JVM , которая оптимизирует размещение элементов и сле дит за тем, чтобы деревья были представлены каноничным и компактным образом. Их представление похоже на векторы тем, что в них также используются деревья, где у каждого узла имеется 32 элемента, или 32 поддерева, но вы бор осуществляется на основе хешкода. Например, самые младшие пять разрядов хешкода ключа используются в целях поиска заданного ключа в отображении для выбора первого поддерева, следующие пять — для вы бора следующего поддерева и т. д. Процесс выбора прекращается, как только 1 Trie происходит от слова retrieval (извлечение) и произносится как «три» или «трай». 2 Steindorfer M. J., Vinju J. J. Optimizing hasharray mapped tries for fast and lean immutable JVM collections // ACM SIGPLAN Notices, volume 50, pages 783–800. ACM, 2015. 544 Глава 24 • Углубленное изучение коллекций у всех элементов, хранящихся в узле, будет хешкод, отличающийся от всех остальных в разрядах, выбранных до сих пор. Таким образом, не обязательно используются все разряды хешкода. Хешизвлечения позволяют достичь хорошего баланса между достаточно быстрым поиском и достаточно эффективными функциональными встав ками ( + ) и удалениями ( - ). Именно поэтому в Scala они положены в основу реализаций по умолчанию неизменяемых отображений и множеств. Факти чески для неизменяемых множеств и отображений, содержащих менее пяти элементов, в Scala предусматривается дальнейшая оптимизация. Множества и отображения, содержащие от одного до четырех элементов, хранятся как отдельные объекты, содержащие эти элементы (или в случае с отображения ми — пары «ключ — значение») в виде полей. Пустое изменяемое множество и пустое изменяемое отображение во всех случаях являются объектами одиночками — не нужно дублировать для них место хранения, поскольку пустые неизменяемые множество или отображение всегда будут оставаться пустыми. Красно-черные деревья Форма сбалансированных двоичных деревьев — красночерные деревья, в ко торых одни узлы обозначены как красные, а другие — как черные. Операции над ними, как и над любыми другими сбалансированными двоичными дере вьями, гарантированно завершаются за время, экспоненциально зависящее от размера дерева. Scala предоставляет реализации множеств и отображений, во внутреннем представлении которых используется красночерное дерево. Доступ к ним осуществляется по именам TreeSet и TreeMap : val set = collection.immutable.TreeSet.empty[Int] set + 1 + 3 + 3 // TreeSet(1, 3) Кроме того, красночерные деревья в Scala — стандартный механизм реали зации SortedSet , поскольку предоставляют весьма эффективный итератор, возвращающий все элементы множества в отсортированном виде. Неизменяемые битовые множества Битовое множество представляет коллекцию небольших целых чисел в виде битов большего целого числа. Например, битовое множество, содержащее 24 .7 . Конкретные классы неизменяемых коллекций 545 3, 2 и 0, будет представлено в двоичном виде как целое число 1101, которое в десятичном виде является числом 13. Во внутреннем представлении битовые множества используют массив из 64разрядных Long значений. Первое Long значение в массиве предназначе но для целых чисел от 0 до 63, второе — от 64 до 127 и т. д. Таким образом, битовые множества очень компактны, поскольку самое большое целое число в множестве чуть меньше нескольких сотен или около того. Операции над битовыми множествами выполняются очень быстро. Про верка на присутствие занимает постоянное время. На добавление элемента в множество уходит время, пропорциональное количеству Long значений в массиве битового множества, которых обычно немного. Некоторые при меры использования битового множества выглядят следующим образом: val bits = scala.collection.immutable.BitSet.empty val moreBits = bits + 3 + 4 + 4 // BitSet(3, 4) moreBits(3) // true moreBits(0) // false Векторные отображения VectorMap (векторное отображение) представляет отображение с использова нием как вектора (для ключей), так и HashMap . Оно предоставляет итератор, возвращающий все элементы в том порядке, в котором они были вставлены. import scala.collection.immutable.VectorMap val vm = VectorMap.empty[Int, String] val vm1 = vm + (1 –> "one") // VectorMap(1 –> one) val vm2 = vm1 + (2 –> "two") // VectorMap(1 –> one, 2 –> two) vm2 == Map(2 –> "two", 1 –> "one") // true В первых строчках видно, что содержимое VectorMap сохраняет порядок вставки, а последняя строчка показывает, что векторные отображения мож но сравнивать с другими видами отображений и в ходе этого сравнения не учитывается порядок следования элементов. Списочные отображения Списочное отображение представляет собой отображение в виде связанно го списка пар «ключ — значение». Как правило, операции над списочными отображениями могут потребовать перебора всего списка. В связи с этим такие операции занимают время, пропорциональное размеру отображения. 546 Глава 24 • Углубленное изучение коллекций Списочные отображения не нашли в Scala широкого применения, посколь ку работа со стандартными неизменяемыми отображениями почти всегда выполняется быстрее. Единственно возможное положительное отличие наблюдается в том случае, если по какойто причине отображение сконстру ировано так, что первые элементы списка выбираются гораздо чаще других элементов. val map = collection.immutable.ListMap(1 –> "one", 2 –> "two") map(2) // "two" 24 .8 . Конкретные классы изменяемых коллекций Изучив наиболее востребованные из имеющихся в стандартной библиотеке Scala классы неизменяемых коллекций, рассмотрим классы изменяемых коллекций. Буферы массивов Буферы массивов уже встречались нам в разделе 15.1. В таком буфере со держатся массив и его размер. Большинство операций над буферами мас сивов выполняются с такой же скоростью, что и над массивами, поскольку эти операции просто обращаются к обрабатываемому массиву и вносят в него изменения. Кроме того, у буфера массива могут быть данные, весьма эффективно добавляемые в его конец. Добавление записи в буфер массива занимает амортизированно постоянное время. Из этого следует, что буферы массивов хорошо подходят для эффективного создания больших коллекций, когда новые элементы всегда добавляются в конец. Вот как выглядят неко торые примеры их применения: val buf = collection.mutable.ArrayBuffer.empty[Int] buf += 1 // ArrayBuffer(1) buf += 10 // ArrayBuffer(1, 10) buf.toArray // Array(1, 10) Буферы списков В разделе 15.1 нам встречались и буферы списков. Буфер списка похож на буфер массива, за исключением того, что внутри него используется не мас сив, а связанный список. Если сразу после создания буфер предполагается 24 .8 . Конкретные классы изменяемых коллекций 547 превращать в список, то лучше воспользоваться буфером списка, а не буфе ром массива. Вот как выглядит соответствующий пример 1 : val buf = collection.mutable.ListBuffer.empty[Int] buf += 1 // ListBuffer(1) buf += 10 // ListBuffer(1, 10) buf.toList // List(1, 10) Построители строк По аналогии с тем, что буфер массива используется для создания массивов, а буфер списка — для создания списков, построитель строк применяется для создания строк. Построители строк используются настолько часто, что за ранее импортируются в пространство имен по умолчанию. Создать их можно с помощью простого выражения new StringBuilder : val buf = new StringBuilder buf += 'a' // a buf ++= "bcdef" // abcdef buf.toString // abcdef ArrayDeque ArrayDeque — изменяемая последовательность, которая поддерживает эф фективное добавление элементов в начало и в конец. Внутри она использует массив изменяемого размера. Если вам нужно вставлять элементы в начало или в конец буфера, то используйте ArrayDeque вместо ArrayBuffer Очереди Наряду с неизменяемыми очередями в Scala есть и изменяемые. Использу ются они аналогично, но для добавления элементов вместо enqueue приме няются операторы += и ++= . Кроме того, метод dequeue будет просто удалять из изменяемой очереди головной элемент и возвращать его. Примеры ис пользования даны ниже: val queue = new scala.collection.mutable.Queue[String] queue += "a" // Queue(a) 1 Появляющийся в ответах интерпретатора в этом и в нескольких других примерах раздела buf.type является синглтонтипом. Как сказано в разделе 7.6, buf.type означает, что переменная содержит именно тот объект, на который указывает buf |