Scala. Профессиональное программирование 2022. Одерски Мартин, Спун Лекс, Веннерс Билл, Соммерс ФрэнкО41 Scala. Профессиональное программирование. 5е изд спб. Питер, 2022. 608 с. ил. Серия Библиотека программиста
 Скачать 6.24 Mb.
|
|
Таблица 24.12. Характеристики производительности типов последовательностей Операции head tail apply update prepend append insert Неизменяемые List C C L L C L — LazyList C C L L C L — ArraySeq C L C L L L — Vector eC eC eC eC eC eC — Queue aC aC L L L C — Range C C C — — — — String C L C L L L — Изменяемые ArrayBuffer C L C C L aC L ListBuffer C L L L C C L StringBuilder C L C C L aC L Queue C L L L C C L ArraySeq C L C C — — — Stack C L L L C L L Array C L C C — — — ArrayDeque C L C C aC aC L 24 .11 . Характеристики производительности 557 Таблица 24.13. Характеристики производительности типов множеств и отображений Операции lookup add remove min Неизменяемые HashSet/HashMap eC eC eC L TreeSet/TreeMap Log Log Log Log BitSet C L L eC a VectorMap eC eC aC L ListMap L L L L Изменяемые HashSet/HashMap eC eC eC L WeakHashMap eC eC eC L BitSet C aC C eC a a Если биты плотно упакованы. Записи в этих двух таблицах расшифровываются следующим образом: C операция занимает постоянное (короткое) время; eC операция занимает эффективно постоянное время, но это может зависеть от некоторых допущений, таких как максимальная длина вектора или распределение хешключей; aC операция занимает амортизированное постоянное время. Неко торые вызовы операции могут занимать больше времени, но если выполняется множество операций, то берется только постоянное среднее время, затрачиваемое на одну операцию; Log на операцию уходит время, пропорциональное логарифму размера коллекции; L операция имеет линейный характер, то есть на нее уходит время, пропорциональное размеру коллекции; – операция не поддерживается. В табл. 24.12 рассматриваются как неизменяемые, так и изменяемые типы последовательностей со следующими операциями: head выбор первого элемента последовательности; tail создание новой последовательности, содержащей все элементы, за исключением первого; apply индексирование; 558 Глава 24 • Углубленное изучение коллекций update функциональное обновление (с помощью метода updated ) для неизменяемых последовательностей, обновление с побочными эффектами (с помощью метода update ) для изменяемых; prepend добавление элемента в начало последовательности. Если по следовательность неизменяемая, то данная операция приводит к созданию новой последовательности. Если изменяемая, то существующая последовательность изменяется; append добавление элемента в конец последовательности. Если по следовательность неизменяемая, то данная операция приводит к созданию новой последовательности. Если изменяемая, то существующая последовательность изменяется; insert вставка элемента в произвольную позицию последовательности. Поддерживается только для изменяемых последовательностей. В табл. 24.13 рассматриваются как неизменяемые, так и изменяемые типы множеств и отображений со следующими операциями: lookup проверка на наличие элемента в множестве или выбор значения, связанного с ключом; add добавление нового элемента в множество или новой пары «ключ — значение» в отображение; remove удаление элемента из множества или ключа из отображения; min наименьший элемент множества или наименьший ключ отобра жения. 24 .12 . Равенство В библиотеках коллекций соблюдается единообразный подход к равенству и хешированию. В первую очередь идея заключается в разбиении коллекций на категории: множества, отображения и последовательности. Коллекции из разных категорий всегда не равны. Например, коллекция Set(1, 2, 3) не равна коллекции List(1, 2, 3) даже притом, что они содержат одни и те же элементы. В то же время внутри одной и той же категории коллекции равны лишь при условии, что содержат одинаковые элементы (для после довательностей — одинаковые элементы, в одинаковом порядке), например List(1, 2, 3) == Vec tor(1, 2, 3) и HashSet(1, 2) == TreeSet(2, 1) При проверке равенства неважно, является коллекция изменяемой или не изменяемой. Для изменяемых коллекций равенство просто зависит от содер 24 .13 . Представления 559 жащихся в ней элементов на момент выполнения проверки на равенство. Это значит, что в разное время изменяемая коллекция может быть равна разным коллекциям в зависимости от того, какие элементы были добавлены или уда лены. Данное обстоятельство может стать ловушкой в случае использования изменяемых коллекций в качестве ключа в хешотображении. Например: import collection.mutable.{HashMap, ArrayBuffer} val buf = ArrayBuffer(1, 2, 3) val map = HashMap(buf –> 3) // Map((ArrayBuffer(1, 2, 3),3)) map(buf) // 3 buf(0) += 1 map(buf) // java.util.NoSuchElementException: key not found: // ArrayBuffer(2, 2, 3) В данном примере выбор, сделанный в последней строке, скорее всего, за вершится сбоем, поскольку хешкод массива xs в предпоследней строке из менился. Поэтому при поиске на основе хешкода будет отыскиваться другое место, отличное от того, в котором был сохранен xs 24 .13 . Представления Коллекции имеют всего несколько методов, которые конструируют новые коллекции. В качестве примеров можно привести map , filter и ++ . Такие методы мы называем преобразователями, поскольку они получают как мини мум одну коллекцию в качестве объектаполучателя и создают в результате своей работы другую. Преобразователи можно реализовать двумя основными способами — строгим и нестрогим (или ленивым). Строгий преобразователь создает новую коллек цию со всеми ее элементами. А нестрогий создает только заместитель получа емой в результате коллекции, а ее элементы конструируются по требованию. В качестве примера нестрогого преобразователя рассмотрим следующую реализацию ленивой операции map : def lazyMap[T, U](col: Iterable[T], f: T => U) = new Iterable[U]: def iterator = col.iterator.map(f) Обратите внимание на то, что lazyMap создает новый объект типа Iterable , не прибегая к обходу всех элементов заданной коллекции coll . Вместо этого заданная функция f применяется к элементам итератора iterator новой коллекции по мере их востребованности. 560 Глава 24 • Углубленное изучение коллекций По умолчанию коллекции в Scala — строгие во всех своих проявлениях, за исключением LazyList , в которой все методы преобразования реализо ваны лениво. Но существует систематический подход для превращения каждой коллекции в ленивую и наоборот, основанный на представлениях коллекций. Представление — это особая разновидность коллекции, которая изображает какуюлибо основную коллекцию, но реализует все ее преоб разователи лениво. Для перехода от коллекции к ее представлению можно воспользовать ся методом view . Если xs — некая коллекция, то xs.view создает точно такую же коллекцию, но с ленивой реализацией всех преобразователей. Перейти обратно от представления к строгой коллекции можно с по мощью операции приведения с фабрикой строгих коллекций в качестве параметра. В качестве примера предположим, что имеется вектор Int значений, в от ношении которого нужно последовательно применить две функции map : val v = Vector((1 to 10)*) // Vector(1, 2, 3, 4, 5, 6, 7, 8, 9, 10) v.map(_ + 1).map(_ * 2) // Vector(4, 6, 8, 10, 12, 14, 16, 18, 20, 22) В последней инструкции выражение v map (_ + 1) создает новый вектор, который второй вызов map (_ * 2) преобразует в третий вектор. Во многих ситуациях создание промежуточного результата из первого вызова map представляется неэкономным. В надуманном примере быстрее было бы вос пользоваться одним вызовом map в сочетании с двумя функциями, (_ + 1) и (_ * 2) . При наличии двух функций, доступных в одном и том же месте, это можно сделать самостоятельно. Но довольно часто последовательные преобразования структур данных выполняются в различных программных модулях. Объединение этих преобразований может разрушить модульность. Более универсальный способ избавления от промежуточных результатов заключается в том, что сначала вектор превращается в представление, затем к представлению применяются все преобразования, после чего оно опять преобразуется в вектор: (v.view.map(_ + 1).map(_ * 2)).toVector // Vector(4, 6, 8, 10, 12, 14, 16, 18, 20, 22) Мы вновь поочередно выполним эту последовательность операций: scala> val vv = v.view val vv: scala.collection.IndexedSeqView[Int] = IndexedSeqView( 24 .13 . Представления 561 Применение v.view выдает значение типа IndexedSeqView , то есть лениво вычисляемую IndexedSeq последовательность. Как и в случае с LazyList , применение toString к представлениям не приводит к вычислению их элементов. Вот почему элементы vv выводятся на экран как Применение первого метода map к представлению дает следующий результат: scala> vv.map(_ + 1) val res13: scala.collection.IndexedSeqView[Int] = IndexedSeqView( Результат выполнения map — другое значение IndexedSeqView[Int] . По сути, это оболочка, которая записывает тот факт, что map с функцией (_ + 1) нуж но применить к вектору v . Но этот метод map не применяется, пока не будет принудительно создано представление. Теперь применим к последнему результату второй метод map : scala> res13.map(_ * 2) val res14: scala.collection.IndexedSeqView[Int] = IndexedSeqView( И наконец, принудительное получение последнего результата приводит к следующему диалогу: scala> res14.toVector val res15: Seq[Int] = Vector(4, 6, 8, 10, 12, 14, 16, 18, 20, 22) Обе сохраненные функции, (_ + 1) и (_ * 2) , применяются как часть выпол нения операции to , и создается новый вектор. При таком способе промежу точные структуры данных не нужны. Операции преобразования, применяемые к представлению, не создают новую структуру данных. Вместо этого они возвращают объект Iterable , итератор которого является результатом применения операции преобразования к ите ратору исходной коллекции. Потребность в использовании представлений обусловлена производительно стью. Вы видели, что с помощью переключения коллекции на представление удалось избежать создания промежуточных результатов. Такая экономия мо жет сыграть весьма важную роль. В качестве еще одного примера рассмотрим задачу поиска первого палиндрома в списке слов. Палиндромом называется слово, которое читается в обратном порядке точно так же, как и в прямом. Необходимые для этого определения имеют следующий вид: def isPalindrome(x: String) = x == x.reverse def findPalindrome(s: Iterable[String]) = s.find(isPalindrome) 562 Глава 24 • Углубленное изучение коллекций Теперь предположим, что имеется весьма длинная последовательность слов и нужно найти палиндром в первом ее миллионе слов. Можно ли повторно воспользоваться определением findPalindrome ? Разумеется, можно создать следующий код: findPalindrome(words.take(1000000)) Он неплохо разделяет два аспекта, заключающихся в получении первого миллиона слов последовательности и поиска в них палиндрома. Но у этого решения есть недостаток: всегда будет создаваться промежуточная по следовательность, состоящая из миллиона слов, даже если первое ее слово уже является палиндромом. Следовательно, потенциально получается, что 999 999 слов копируются в промежуточный результат, не подвергаясь по следующей проверке. Многие программисты откажутся от этого и напишут собственную специализированную версию поиска палиндрома в некоем заданном префиксе последовательности аргументов. Но с представления ми этого делать не придется. Нужно просто воспользоваться следующим кодом: findPalindrome(words.view.take(1000000)) Здесь также неплохо разрешен конфликт интересов, но вместо последо вательности из миллиона элементов будет создан отдельный легковесный объект представления. Таким образом, вам не придется выбирать между производительностью и модульностью. После того как вы увидели все эти интересные примеры использования пред ставлений, у вас может возникнуть вопрос: а зачем вообще нужны строгие коллекции? Одна из причин состоит в том, что сравнение производительно сти не всегда бывает в пользу ленивых коллекций. Для коллекций меньших размеров добавленные издержки на формирование и применение замыканий в представлениях зачастую выше, чем выгоды, получаемые за счет того, что в них не применяются промежуточные структуры данных. Возможно, еще более существенной причиной является то, что вычисления в представле ниях могут создавать серьезные помехи, если у отложенных операций есть побочные эффекты. Вот пример, о который обожглись многие пользователи Scala версий до 2.8. В этих версиях тип Range был ленивым, поэтому вел себя, по сути, как пред ставление. Программисты пробовали создавать такие вот акторы 1 : val actors = for i <- 1 to 10 yield actor { ??? } 1 Библиотека акторов Scala устарела, но этот исторический прием все еще актуален. 24 .14 . Итераторы 563 А потом удивлялись, почему впоследствии ни один из акторов не выполнял ся, даже если метод actor должен создавать и запускать актор из следующего за ним кода, заключенного в фигурные скобки. Чтобы понять, почему ничего не происходит, вспомним, что показанное ранее выражение for эквивалентно применению метода map , показанного ниже: val actors = (1 to 10).map(i => actor { ??? }) Поскольку ранее диапазон, созданный выражением (1 to 10) , вел себя подоб но представлению, результатом выполнения map опять было представление. То есть элементы не вычислялись, а следовательно, акторы не создавались! Они создавались бы с помощью принудительного вычисления всего диапа зона, но далеко не очевидно, что это нужно для того, чтобы заставить акторов сделать их работу. Чтобы избегать подобных сюрпризов, коллекции Scala в версии 2.8 полу чили более простые правила. Все коллекции, за исключением ленивых спи сков и представлений, являются строгими. Перейти от строгой коллекции к ленивой можно только через метод представления view . Единственный способ перейти обратно — применить метод to . Следовательно, акторы, определенные ранее, в Scala 2.8 поведут себя ожидаемым образом, то есть будут созданы и запущены десять акторов. Чтобы вернуться к прежнему парадоксальному поведению, придется добавить явный вызов метода view : val actors = for i <- (1 to 10).view yield actor { ??? } В целом представления — весьма эффективный инструмент, позволяю щий увязать соображения эффективности с соображениями модульности. Но чтобы не путаться в тонкостях отложенных вычислений, применение представлений лучше ограничить чисто функциональным кодом, в котором у преобразований коллекций нет побочных эффектов. И лучше избегать смешивания представлений и операций, создающих новые коллекции, если у них к тому же есть побочные эффекты. 24 .14 . Итераторы Итератор — это не коллекция, а, скорее, способ поочередного обращения к элементам коллекции. Двумя базовыми операциями итератора являют ся next и hasNext . Вызов it.next() вернет следующий элемент итератора и продвинет итератор дальше. Затем при повторном вызове next в отно шении того же итератора будет выдан элемент, следующий за тем, кото рый был возвращен ранее. Если возвращать станет нечего, то вызов next 564 Глава 24 • Углубленное изучение коллекций приведет к генерации исключения NoSuchElementException . Определить, остались ли еще элементы в коллекции, можно с помощью метода hasNext класса Iterator Наиболее простой способ выполнить последовательный перебор всех эле ментов, возвращаемых итератором, — использовать цикл while : while it.hasNext do println(it.next()) Итераторы в Scala также предоставляют аналоги большинства методов, имеющихся в трейтах Iterable и Seq . Например, они предоставляют метод foreach , который выполняет заданную процедуру в отношении каждого эле мента, возвращенного итератором. При использовании foreach показанный ранее цикл можно сократить до следующего кода: it.foreach(println) Как и всегда, в качестве альтернативного синтаксиса для выражений, исполь зующих foreach , map , filter и flatMap , можно воспользоваться выражением for . То есть еще одним способом вывести на экран все элементы, возвращен ные итератором, мог бы быть следующий код: for elem <- it do println(elem) Между методом foreach , применяемым в отношении итераторов, и таким же методом, применяемым к коллекциям, допускающим обход элементов, есть существенная разница: при вызове в отношении итератора foreach оставит итератор в состоянии завершения его работы. Поэтому еще один вызов next в отношении того же самого итератора закончится неудачно и приведет к генерации исключения NoSuchElementException . Напротив, при вызове в отношении коллекции foreach оставляет количество элементов в коллек ции без изменений, если только переданная функция не добавляет или не удаляет элементы, чего делать не рекомендуется, поскольку это легко может привести к неожиданным результатам. Другие операции, общие для Iterator и Iterable , обладают таким же свой ством оставлять итератор в состоянии завершения работы. Например, ите раторы предоставляют метод map , возвращающий новый итератор: val it = Iterator("a", "number", "of", "words") val lit = it.map(_.length) it.hasNext // true lit.foreach(println) // prints 1, 6, 2, 5 it.hasNext // false |