Scala. Профессиональное программирование 2022. Одерски Мартин, Спун Лекс, Веннерс Билл, Соммерс ФрэнкО41 Scala. Профессиональное программирование. 5е изд спб. Питер, 2022. 608 с. ил. Серия Библиотека программиста
 Скачать 6.24 Mb.
|
|
548 Глава 24 • Углубленное изучение коллекций queue ++= List("b", "c") // Queue(a, b, c) queue // Queue(a, b, c) queue.dequeue // a queue // Queue(b, c) Стеки Scala предоставляет изменяемый стек. Ниже представлен пример: val stack = new scala.collection.mutable.Stack[Int] stack.push(1) // Stack(1) stack // Stack(1) stack.push(2) // Stack(2, 1) stack // Stack(2, 1) stack.top // 2 stack // Stack(2, 1) stack.pop // 2 stack // Stack(1) Обратите внимание: в Scala нет поддержки неизменяемых стеков, поскольку данная функциональность уже реализована в списках. Операция push над неизменяемым стеком аналогична выражению a :: для списка. Операция pop — то же самое, что вызов head и tail для списка. Изменяемые ArraySeq Последовательный массив — это изменяемая последовательность фикси рованного размера, которая хранит свои элементы внутри Array[AnyRef] В Scala он реализован в виде класса ArraySeq Данный класс обычно используется в случаях, когда вам нужен производи тельный массив и притом необходимо создавать обобщенные экземпляры последовательности с элементами, тип которых не известен заранее и не может быть получен во время выполнения с помощью ClassTag . С этими проблемами, которые присущи массивам, вы познакомитесь чуть позже, в разделе 24.9. Хеш-таблицы Хештаблица сохраняет свои элементы в образующем ее массиве, помещая каждый в позицию в массиве, определяемую хешкодом этого элемента. На добавление элемента в хештаблицу всегда уходит одно и то же время, 24 .8 . Конкретные классы изменяемых коллекций 549 если только в массиве нет еще одного элемента с точно таким же хешкодом. Поэтому, пока помещенные в хештаблицу элементы имеют хорошее рас пределение хешкодов, работа с ней выполняется довольно быстро. По этой причине типы изменяемых отображений и множеств по умолчанию в Scala основаны на хештаблицах. Хешмножества и хешотображения используются точно так же, как и любые другие множества или отображения. Ниже представлены некоторые простые примеры: val map = collection.mutable.HashMap.empty[Int,String] map += (1 –> "make a web site") // Map(1 –> make a web site) map += (3 –> "profit!") // Map(1 –> make a web site, 3 –> profit!) map(1) // make a web site map.contains(2) // false Конкретный порядок обхода элементов хештаблицы не гарантируется. Выполняется простой обход элементов массива, на котором основана хештаблица, в порядке расположения его элементов. Чтобы получить гарантированный порядок обхода, следует воспользоваться связанными хешотображением или множеством вместо обычных. Связанные хеш отображение или множество почти аналогичны обычным хешотображению или множеству, но включают связанный список элементов в порядке их до бавления. Обход элементов такой коллекции всегда выполняется в том же порядке, в котором они добавлялись в нее изначально. Слабые хеш-отображения Слабое хешотображение представляет собой особую разновидность хеш отображения, в которой сборщик мусора не следует по ссылкам от отобра жения к хранящимся в нем ключам. Это значит, ключ и связанное с ним значение исчезнут из отображения, если на данный ключ нет другой ссылки. Слабые хешотображения используются для решения таких задач, как кэши рование, когда нужно повторно задействовать результат затратной функции в случае повторного вызова функции в отношении того же самого ключа. Если ключи и результаты функции хранятся в обычном хешотображении, то оно может бесконечно разрастись и никакие ключи никогда не станут мусо ром. Этой проблемы удается избежать с помощью слабого хешотображения. Как только объект ключа становится недоступным, связанная с ним запись удаляется из такого отображения. Слабые хешотображения реализованы 550 Глава 24 • Углубленное изучение коллекций в Scala в виде обертки положенной в их основу Javaреализации java.util.We- akHashMap Совместно используемые отображения К совместно используемому отображению могут обращаться сразу несколько потоков. В дополнение к обычным операциям с Map это отображение предо ставляет атомарные операции (табл. 24.11). Таблица 24.11. Операции в трейте concurrent .Map Что Что делает m.putIfAbsent(k, v) Добавляет привязку «ключ — значение» k –> v , кроме тех случаев, когда k уже определен в m m.remove(k, v) Удаляет запись для ключа k , если он в данный момент отображен на значение v m.replace(k, old, new) Заменяет значение, связанное с k , новым значением new , если ранее с ключом было связано значение old m.replace(k, v) Заменяет значение, связанное с k , значением v , если ранее этот ключ был связан с какимлибо значением Трейт scala.concurrent.Map определяет интерфейс для изменяемых отобра жений с поддержкой конкурентного доступа. Стандартная библиотека пред лагает две реализации этого трейта. Первая — это java.util.concurrent.Con- currentMap из Java, которую можно автоматически превратить в отображение языка Scala, используя стандартные для Java/Scala операции приведения коллекций (эти преобразования будут описаны в разделе 24.16). Вторая реализация, TrieMap , основана на HAMT без блокировок. Изменяемые битовые множества Изменяемое битовое множество похоже на неизменяемое, но отличается тем, что может быть изменено на месте. По сравнению с неизменяемым оно работает при обновлениях немного эффективнее, поскольку неизмененные Long значения копировать не нужно. Пример использования выглядит так: val bits = scala.collection.mutable.BitSet.empty bits += 1 // BitSet(1) bits += 3 // BitSet(1, 3) bits // BitSet(1, 3) 24 .9 . Массивы 551 24 .9 . Массивы Массивы в Scala — особая разновидность коллекции. С одной стороны, мас сивы Scala в точности соответствуют массивам Java. То есть Scalaмассив Ar ray[Int] представлен как Javaмассив int[] , Array[Double] — как double[] , а Ar ray[String] — как String[] . Но вместе с тем массивы Scala предостав ляют гораздо больше, чем их Javaаналоги. Вопервых, массивы Scala могут быть обобщенными. То есть можно воспользоваться массивом Array[T] , где T является параметром типа или абстрактным типом. Вовторых, массивы Scala совместимы со Scalaпоследовательностями, то есть туда, где требу ется Seq[T] , можно передавать Array[T] . И наконец, массивы Scala также поддерживают все операции с последовательностями. Приведем несколько практических примеров: val a1 = Array(1, 2, 3) val a2 = a1.map(_ * 3) // Array(3, 6, 9) val a3 = a2.filter(_ % 2 != 0) // Array(3, 9) a3.reverse // Array(9, 3) Если учесть, что массивы Scala представлены точно так же, как массивы Java, то как эти дополнительные свойства могут поддерживаться в Scala? Ответ заключается в систематическом использовании неявных преобразова ний. Массив не может претендовать на то, чтобы быть последовательностью, поскольку тип данных, представляющих настоящий массив, не является под типом типа Seq . Вместо этого там, где массив будет использоваться в качестве последовательности Seq , он будет неявно обернут в подкласс класса Seq . Имя этого подкласса — scala.collection.mutable.ArraySeq . Вот как это работает: val seq: collection.Seq[Int] = a1 // ArraySeq(1, 2, 3) val a4: Array[Int] = seq.toArray // Array(1, 2, 3) a1 eq a4 // false Сеанс работы с интерпретатором показывает, что массивы совместимы с последовательностями благодаря неявному преобразованию из Array в ArraySeq . Преобразование в обратном направлении, из ArraySeq в Array , можно выполнить с использованием метода toArray , который определен в классе Iterable . В последней строке приведенного ранее диалога с интер претатором показано, что заключенный в оболочку массив при его изъятии оттуда с помощью метода toArray возвращает копию исходного массива. Есть еще одно неявное преобразование, применимое к массивам. Оно просто «добавляет» к массивам все методы, применимые к последовательностям, но сами массивы в последовательности не превращает. «Добавляет» означает, 552 Глава 24 • Углубленное изучение коллекций что массив заворачивается в другой объект типа ArrayOps , который поддер живает все методы работы с последовательностями. Обычно этот ArrayOps объект существует весьма непродолжительное время — он становится недо ступен после вызова метода для работы с последовательностью, и его место хранения может быть использовано повторно. Современные виртуальные машины зачастую вообще избегают создания таких объектов. Разница между этими двумя неявными преобразованиями массивов пока зана в следующем примере: val seq: collection.Seq[Int] = a1 // ArraySeq(1, 2, 3) seq.reverse // ArraySeq(3, 2, 1) val ops: collection.ArrayOps[Int] = a1 // Array(1, 2, 3) ops.reverse // Array(3, 2, 1) Как видите, при вызове метода reverse в отношении объекта seq типа ArraySeq опять будет получен объект типа ArraySeq . Это не противоречит здравому смыслу, поскольку массивы ArraySeq , заключенные в оболочку, относятся к типам Seq , а вызов метода reverse в отношении любого Seq объекта вновь даст Seq объект. В то же время вызов метода reverse в от ношении значения ops класса ArrayOps приведет к возвращению значения типа Array , а не Seq Приведенный ранее пример с ArrayOps был надуманным, предназначенным лишь для демонстрации разницы с ArraySeq . В обычной ситуации вы бы не стали определять значение класса ArrayOps , а просто вызвали бы в отноше нии массива метод из класса Seq : a1.reverse // Array(3, 2, 1) Объект ArrayOps вставляется автоматически в ходе неявного преобразова ния. Следовательно, показанная выше строка кода эквивалентна следующей строке, где метод intArrayOps является преобразованием, которое неявно вставлялось в предыдущем примере: intArrayOps(a1).reverse // Array(3, 2, 1) Возникает вопрос, касающийся способа выбора компилятором intArrayOps в показанной выше строке среди других неявных преобразований в ArraySeq Ведь оба преобразования отображают массив на тип, поддерживающий метод reverse , указанный во введенном коде. Ответ на данный вопрос — уровни приоритета этих двух преобразований. У преобразования ArrayOps более высокий приоритет, чем у ArraySeq . Первое преобразование определено в объекте Predef , а второе — в классе scala.LowPriorityImplicits , явля ющемся суперклассом для Predef . Неявные преобразования в подклассах 24 .9 . Массивы 553 и подобъектах имеют приоритет над неявными преобразованиями в базовых классах. Следовательно, если применимы оба преобразования, то будет вы брано то, которое определено в Predef . Очень похожая схема, рассмотренная в разделе 21.7, работает для строк. Теперь вы знаете, что массивы совместимы с последовательностями и могут поддерживать все операции, применяемые к последовательностям. А как на счет обобщенности? В Java вы не можете воспользоваться записью T[] , где T представляет собой параметр типа. А как же тогда представлен имеющийся в Scala тип Array[T] ? Фактически такой обобщенный массив, как Array[T] , может во время выполнения программы стать любым из восьми примитив ных типов массивов Java: byte[] , short[] , char[] , int[] , long[] , float[] , double[] , boolean[] — или же стать массивом объектов. Единственный об щий тип, охва тывающий во время выполнения программы все эти типы, — AnyRef (или его аналог java.lang.Object ), следовательно, это именно тот тип, на который компилятор Scala отображает Array[T] . Во время выполнения программы, когда происходит обращение к элементу массива типа Array[T] или обновление этого элемента, производится ряд проверок на соответствие типам. Благодаря этому определяется действительный тип массива, а затем выполняется корректная операция уже над Javaмассивом. Проверки на соответствие типам несколько замедляют операции над массивами. Можно ожидать, что обращения к обобщенным массивам будут в тричетыре раза медленнее обращений к простым массивам или массивам объектов. Сле довательно, если требуется максимально высокая производительность, то предпочтение следует отдавать конкретным, а не обобщенным массивам. Но одного представления типа обобщенного массива недостаточно, дол жен существовать также способ создания обобщенных массивов. А это еще более сложная задача, которая требует от вас оказать некоторую помощь. В качестве примера рассмотрим попытку создания метода, работающего с обобщениями и создающего массив: // Неправильно! def evenElems[T](xs: Vector[T]): Array[T] = val arr = new Array[T]((xs.length + 1) / 2) for i <- 0 until xs.length by 2 do arr(i / 2) = xs(i) arr Метод evenElems возвращает новый массив, состоящий из тех элементов используемого в качестве аргумента вектора xs , которые находятся в нем на четных позициях. В первой строке тела метода evenElems создается получа емый в результате массив, имеющий тот же тип элементов, что и аргумент. Следовательно, в зависимости от фактического параметра типа для T это 554 Глава 24 • Углубленное изучение коллекций может быть Array[Int] , или Array[Boolean] , или массив из других прими тивных типов Java, или же массив какогонибудь ссылочного типа. Но все эти типы имеют во время выполнения программы различные представления, поэтому возникает вопрос: как среда выполнения Scala собирается выбирать из них нужное? По сути, сделать это, основываясь на имеющейся инфор мации, она не может, поскольку фактический тип, который соответствует параметру типа T , во время выполнения кода затирается. Поэтому при по пытке скомпилировать показанный ранее код будет получено следующее сообщение об ошибке: 2 | val arr = new Array[T]((xs.length + 1) / 2) | ˆ | No ClassTag available for T Здесь вам следует помочь компилятору, предоставив подсказку времени выполнения о том, какой параметр типа у evenElems . Эта подсказка прини мает форму тега класса типа scala.reflect.ClassTag . Тег класса описывает заданный исполняемый класс, предоставляя исчерпывающую информацию о нем конструктору массива. Во многих случаях компилятор может создавать тег класса самостоятель но. Именно так обстоит дело с конкретными типами наподобие Int или String . То же распространяется и на некоторые обобщенные типы наподо бие List[T] , где для выстраивания предположения об исполняемом классе информации вполне достаточно; в данном примере исполняемым классом будет List Для полностью обобщенных случаев обычно практикуется передача тега класса с помощью контекстного ограничителя, рассмотренного в разде ле 23.2. А вот как, используя этот ограничитель, можно исправить показанное ранее определение: // Этот код работает import scala.reflect.ClassTag def evenElems[T: ClassTag](xs: Vector[T]): Array[T] = val arr = new Array[T]((xs.length + 1) / 2) for i <- 0 until xs.length by 2 do arr(i / 2) = xs(i) arr В этом новом определении компилятор при создании Array[T] ищет тег класса для параметра типа T , то есть будет искать неявное значение типа ClassTag[T] . Если такое значение будет найдено, то тег класса будет исполь зован для создания массива нужного вида. В противном случае вы увидете сообщение об ошибке, похожее на показанное ранее. 24 .10 . Строки 555 Вот как выглядит диалог с интерпретатором, в котором используется метод evenElems : evenElems(Vector(1, 2, 3, 4, 5)) // Array(1, 3, 5) evenElems(Vector("this", "is", "a", "test", "run")) // Array(this, a, run) В обоих случаях компилятор Scala автоматически создает тег класса для типа элемента (сначала Int , потом String ) и передает его неявному параметру мето да evenElems . Компилятор может сделать то же самое для всех конкретных ти пов, но не способен на это, если сам аргумент является еще одним параметром типа без признака класса. Например, следующий код не пройдет компиляцию: scala> def wrap[U](xs: Vector[U]) = evenElems(xs) 1 |def wrap[U](xs: Vector[U]) = evenElems(xs) | ˆ | No ClassTag available for U Здесь метод evenElems получает тег класса для параметра типа U , но ничего не находит. Разумеется, решение в данном случае — потребовать еще один неяв ный тег класса для U . Код, представленный ниже, уже пройдет компиляцию: def wrap[U: ClassTag](xs: Vector[U]) = evenElems(xs) Этот пример показывает также, что контекстное ограничение в определе нии U — краткая форма неявного параметра, названного здесь evidence$1 и имеющего тип ClassTag[U] 24 .10 . Строки Как и массивы, строки не являются последовательностями в прямом смысле слова, но могут быть в них преобразованы и вдобавок поддерживают все операции с последовательностями. Ниже приводятся примеры операций, которые могут вызываться в отношении строк: val str = "hello" str.reverse // olleh str.map(_.toUpper) // HELLO str.drop(3) // lo str.slice(1, 4) // ell val s: Seq[Char] = str // hello Эти операции поддерживаются двумя неявными преобразованиями, рассмо тренными в разделе 23.5. Первое, имеющее более низкий уровень приорите та, отображает класс String на класс WrappedString , являющийся подклассом 556 Глава 24 • Углубленное изучение коллекций immutable.IndexedSeq . Это преобразование было применено в последней строке предыдущего примера, в котором строка была преобразована в значе ние типа Seq . Другое преобразование, с более высоким уровнем приоритета, отображает строку на объект StringOps , который добавляет к строкам все методы, применяемые к неизменяемым последовательностям. В предыду щем примере это преобразование было неявно вставлено в вызовы методов reverse , map , drop и slice 24 .11 . Характеристики производительности Как показали все предыдущие разъяснения, разным типам коллекций свойственны различные характеристики производительности. Именно это обстоя тельство становится главной причиной выбора конкретного типа коллекции из множества других типов. Характеристики производительности некоторых наиболее востребованных операций над коллекциями сведены в табл. 24.12 и 24.13. |