Предисловие

Там есть обзорная коллекция 2.8 Мартина Одерски, которая, вероятно, должна быть вашей первой ссылкой. Он также дополнен архитектурными заметками , которые будут особенно интересны тем, кто хочет создавать свои собственные коллекции.

Остальная часть этого ответа была написана задолго до того, как такая вещь существовала (фактически, до того, как была выпущена сама 2.8.0).

Вы можете найти статью об этом как Scala SID # 3 . Другие статьи в этой области также должны быть интересны людям, интересующимся различиями между Scala 2.7 и 2.8.

Я процитирую статью выборочно и дополню некоторыми своими мыслями. Есть также некоторые изображения, созданные Матиасом на decodified.com, и исходные файлы SVG можно найти здесь .

Сами классы / черты коллекций

На самом деле существует три иерархии черт для коллекции: одна для изменяемых коллекций, одна для неизменяемых коллекций и одна, которая не делает никаких предположений относительно коллекций.

Также существует различие между параллельным, последовательные и возможно-параллельные коллекции, представленные в Scala 2.9. О них я расскажу в следующем разделе. Иерархия, описанная в этом разделе, относится исключительно к непараллельным коллекциям .

На следующем изображении показана неспецифическая иерархия, представленная в Scala 2.8:

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

График неизменной иерархии:

График изменяемой иерархии:

Легенда:

Вот сокращенное ASCII-изображение иерархии коллекций для тех, кто не может видеть изображения.

                    Traversable
                         |
                         |
                      Iterable
                         |
      +------------------+--------------------+
     Map                Set                  Seq
      |                  |                    |
      |             +----+----+         +-----+------+
    Sorted Map  SortedSet   BitSet   Buffer Vector LinearSeq

Параллельные коллекции

Когда в Scala 2.9 были представлены параллельные коллекции, одной из целей дизайна было сделать их использование максимально бесшовным. Проще говоря, можно заменить непараллельную (последовательную) коллекцию на параллельную и мгновенно извлечь выгоду.

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

Две новые иерархии были созданы для поддержки параллельных коллекций.

Иерархия параллельных коллекций имеет те же имена для признаков, но предшествует Par : ParIterable , ParSeq , ParMap и ParSet . Обратите внимание, что не существует ParTraversable , поскольку любая коллекция, поддерживающая параллельный доступ, способна поддерживать более сильный признак ParIterable . У него также нет некоторых более специализированных черт, присутствующих в последовательной иерархии. Вся эта иерархия находится в каталоге scala.collection.parallel .

Классы, реализующие параллельные коллекции, также различаются, с ParHashMap и ParHashSet для обоих изменяемых и неизменяемые параллельные коллекции, а также ParRange и ParVector , реализующие неизменяемый. ParSeq и ParArray , реализующий mutable.ParSeq .

Также существует другая иерархия, которая отражает признаки последовательных и параллельных коллекций, но с префиксом Gen : GenTraversable , GenIterable , GenSeq , GenMap и GenSet . Эти черты являются родителями как параллельных, так и последовательных коллекций. Это означает, что метод, принимающий Seq , не может получить параллельную коллекцию, но ожидается, что метод, принимающий GenSeq , будет работать как с последовательными, так и с параллельными коллекциями.

С учетом того, как они работают. иерархии были структурированы, код, написанный для Scala 2.8, был полностью совместим со Scala 2.9 и требовал последовательного поведения. Без переписывания, он не может использовать преимущества параллельных коллекций, но требуемые изменения очень малы.

Использование параллельных коллекций

Любую коллекцию можно преобразовать в параллельную, вызвав для нее метод par . Точно так же любую коллекцию можно преобразовать в последовательную, вызвав для нее метод seq .

Если коллекция уже была запрошенного типа (параллельная или последовательная), преобразование не произойдет. Однако если вызвать seq для параллельной коллекции или par для последовательной коллекции, то будет сгенерирована новая коллекция с запрошенной характеристикой.

Не путайте seq , который превращает коллекцию в непараллельную коллекцию, с toSeq , который возвращает Seq , созданный из элементов коллекции. Вызов toSeq в параллельной коллекции вернет ParSeq , а не последовательную коллекцию.

Основные черты

Хотя существует множество реализующих классов и субтитров, есть несколько основных черт в иерархии, каждый из которых предоставляет больше методов или более конкретных гарантий, но уменьшает количество классов, которые могли бы их реализовать.

В следующих подразделах я дам краткое описание основных черт и идеи, лежащей в основе их.

Trait TraversableOnce

Этот трейт очень похож на трейт Traversable , описанный ниже, но с ограничением, что вы можете использовать его только один раз . То есть любые методы, вызываемые для TraversableOnce , могут сделать его непригодным для использования.

Это ограничение делает возможным совместное использование одних и тех же методов коллекциями и Итератором . Это позволяет методу, который работает с Iterator , но не использует методы, специфичные для Iterator , на самом деле иметь возможность работать с любой коллекцией вообще, плюс итераторы, если они переписаны для принятия TraversableOnce .

Поскольку TraversableOnce объединяет коллекции и итераторы, он не появляется в предыдущих графиках, которые касаются только коллекций.

Trait Traversable

В вершиной иерархии коллекции является признак Traversable . Его единственная абстрактная операция -

def foreach[U](f: Elem => U)

. Операция предназначена для обхода всех элементов коллекции и применения данной операции f к каждому Это позволяет методу, который работает с Iterator , но не использует методы, специфичные для Iterator , на самом деле иметь возможность работать с любой коллекцией вообще, плюс итераторы, если они переписаны для принятия TraversableOnce .

Поскольку TraversableOnce объединяет коллекции и итераторы, он не появляется в предыдущих графиках, которые касаются только коллекций.

Trait Traversable

В вершиной иерархии коллекции является признак Traversable . Его единственная абстрактная операция -

def foreach[U](f: Elem => U)

. Операция предназначена для обхода всех элементов коллекции и применения данной операции f к каждому Это позволяет методу, который работает с Iterator , но не использует методы, специфичные для Iterator , на самом деле иметь возможность работать с любой коллекцией вообще, плюс итераторы, если они переписаны для принятия TraversableOnce .

Поскольку TraversableOnce объединяет коллекции и итераторы, он не появляется в предыдущих графиках, которые касаются только коллекций.

Trait Traversable

В вершиной иерархии коллекции является признак Traversable . Его единственная абстрактная операция -

def foreach[U](f: Elem => U)

. Операция предназначена для обхода всех элементов коллекции и применения данной операции f к каждому если переписать, чтобы принять TraversableOnce .

Поскольку TraversableOnce объединяет коллекции и итераторы, он не появляется в предыдущих графиках, которые касаются только коллекций.

Trait Traversable

На вершине иерархии коллекции находится признак Traversable . Его единственная абстрактная операция -

def foreach[U](f: Elem => U)

. Операция предназначена для обхода всех элементов коллекции и применения данной операции f к каждому если переписать, чтобы принять TraversableOnce .

Поскольку TraversableOnce объединяет коллекции и итераторы, он не появляется на предыдущих графиках, которые касаются только коллекций.

Trait Traversable

На вершине иерархии коллекции находится признак Traversable . Его единственная абстрактная операция -

def foreach[U](f: Elem => U)

. Операция предназначена для обхода всех элементов коллекции и применения данной операции f к каждому элемент. Приложение сделано только из-за его побочного эффекта; фактически любой результат функции f отбрасывается foreach.

Проходимые объекты могут быть конечными или бесконечными. Примером бесконечного проходимого объекта является поток натуральных чисел Stream.from (0) . Метод hasDefiniteSize указывает, возможно ли, что коллекция бесконечно. Если hasDefiniteSize возвращает истину, набор определенно конечен. Если он возвращает false, Коллекция еще не полностью разработана, поэтому она может быть бесконечной или конечной.

Этот класс определяет методы, которые могут быть эффективно реализованы в терминах foreach (более 40 из них).

Trait Iterable

Эта черта объявляет абстрактный метод итератор , который возвращает итератор, который выводит все элементы коллекции один за другим. Метод foreach в Iterable реализован в виде итератора итератора . Подклассы Iterable часто заменяют foreach прямой реализацией для повышения эффективности.

Класс Iterable также добавляет некоторые менее часто используемые методы к Traversable , которые могут быть реализуется эффективно только при наличии итератора . Они кратко излагаются ниже.

xs.iterator          An iterator that yields every element in xs, in the same order as foreach traverses elements.
xs takeRight n       A collection consisting of the last n elements of xs (or, some arbitrary n elements, if no order is defined).
xs dropRight n       The rest of the collection except xs takeRight n.
xs sameElements ys   A test whether xs and ys contain the same elements in the same order

Другие черты

После Iterable идут три базовых черты, которые наследуются от него: Seq , Set и Map . Все три имеют метод apply , и все три реализуют черту PartialFunction , но значение apply в каждом случае разное.

Я доверяю значению из Seq , Set и Map интуитивно понятен. После них классы разбиваются на конкретные реализации, которые предлагают определенные гарантии в отношении производительности и методов, которые он делает доступными в результате этого. Также доступны некоторые свойства с дополнительными уточнениями, такие как LinearSeq , IndexedSeq и SortedSet .

Список ниже может быть улучшен. Оставьте комментарий с предложениями, и я исправлю его.

Базовые классы и черты

• Traversable - Базовый класс коллекции. Может быть реализовано только с помощью foreach .
  • TraversableProxy - Прокси для Traversable . Просто укажите self на реальную коллекцию.
  • TraversableView - Traversable с некоторыми нестрогими методами.
  • TraversableForwarder - перенаправляет большинство методов в , лежащий в основе , кроме toString , hashCode , равно , stringPrefix , newBuilder , view ] и все вызовы, создающие новый итеративный объект того же типа.
  • mutable.Traversable и immutable.Traversable - то же самое, что Traversable , но с ограничением коллекции type.
  • Существуют другие особые случаи Итерируемые классы, такие как MetaData .
    • IterableProxy , IterableView , изменяемый и неизменяемый.Iterable .
• Iterator - признак, не являющийся потомком Проходимый . Определите следующий и hasNext .
  • CountedIterator - Итератор , определяющий счетчик , который возвращает элементы, которые мы видели до сих пор.
  • BufferedIterator - Определяет заголовок ], который возвращает следующий элемент, не потребляя его.
  • Существуют другие особые случаи Классы итератора , например Источник .

Карты

• Карта ] - Iterable из Tuple2 , который также предоставляет методы для получения значения (второго элемента кортежа) с учетом ключа (первого элемента кортежа). Также расширяет PartialFunction .
  • MapProxy - прокси для карты .
  • DefaultMap - черта, реализующая некоторые из Map абстрактные методы.
  • SortedMap - Карта , ключи которой отсортированы.
    • immutable.SortMap
      • immutable.TreeMap - Класс, реализующий immutable.SortedMap .
  • immutable.Map
    • immutable.MapProxy
    • immutable.HashMap ] - Класс, реализующий immutable.Map посредством хеширования ключей.
    • immutable.IntMap - Класс, реализующий immutable.Map , специализированный для Int ] ключи. Использует дерево на основе двоичных цифр ключей.
    • immutable.ListMap - Класс, реализующий immutable.Map через списки.
    • immutable.LongMap - A класс, реализующий immutable.Map , специализированный для ключей Long . См. IntMap .
    • Существуют дополнительные классы, оптимизированные для определенного количества элементов.
  • mutable.Map
    • mutable. SynchronizedMap - миксин , который следует смешать с Map , чтобы предоставить его версию с синхронизированными методами.
    • mutable.MapProxy .

The Sequences

• Seq - последовательность элементов. Один предполагает четко определенный размер и повторение элементов. Также расширяет PartialFunction .
  • IndexedSeq - последовательности, которые поддерживают доступ к элементу O (1) и вычисление длины O (1).
    • IndexedSeqView
    • immutable.PagedSeq - реализация IndexedSeq , где элементы создаются по запросу функцией, переданной через конструктор.
    • immutable.IndexedSeq
      • immutable.Range - последовательность целых чисел с разделителями, закрытая на нижнем конце, открытая на верхнем конце и с шагом.
        • immutable.Range.Inclusive - A Диапазон также закрыт на высоком уровне.
        • immutable.Range.ByOne - A Диапазон шаг которого равен 1.
      • immutable.NumericRange - более общая версия Range , которая работает с любым интегралом .
        • immutable.NumericRange.Inclusive , immutable.NumericRange.Exclusive .
        • immutable.WrappedString , immutable.RichString - Оболочки, которые позволяют видеть String как Seq [Char] , при этом все еще сохраняя методы String . Я не уверен, в чем разница между ними.
    • mutable.IndexedSeq
      • mutable.GenericArray - Массивная структура на основе Seq . Обратите внимание, что "class" Array - это Java Array , который является скорее методом хранения в памяти, чем классом.
      • mutable.ResizableArray - Внутренний класс, используемый классы, основанные на массивах с изменяемым размером.
      • mutable.PriorityQueue , mutable.
        • immutable.LinearSeq
          • immutable.List - Реализация неизменяемого односвязного списка.
          • immutable.Stream - Ленивый список. Его элементы вычисляются только по запросу, но затем запоминаются (сохраняются в памяти). Теоретически он может быть бесконечным.
        • mutable.LinearSeq
          • mutable.DoublyLinkedList - Список с изменяемым prev , head ( elem ) и tail ( next ).
          • mutable.LinkedList - список с изменяемой головой ( elem ) и хвост ( следующий ).
          • mutable.MutableList - класс, используемый внутри для реализации классов на основе изменяемых списков.
            • mutable.Queue , mutable.QueueProxy - структура данных, оптимизированная для операций FIFO (First-In, First-Out).
            • mutable.QueueProxy - A Прокси для изменяемый.Queue .
      • SeqProxy , SeqView , SeqForwarder
      • immutable.Seq
        • неизменный. Queue - класс, реализующий структуру данных, оптимизированную для FIFO (First-In, First-Out). Не существует общего суперкласса для изменяемых и неизменяемых очередей.
        • immutable.Stack - Класс, реализующий LIFO-оптимизированный (Last-In, First-Out ) структура данных. Не существует общего суперкласса для обоих изменяемых неизменяемых стеков.
        • immutable.Vector -?
        • scala.xml.NodeSeq - специализированный XML-класс, который extends неизменяемый. Seq .
        • immutable.IndexedSeq - Как показано выше.
        • immutable.LinearSeq - Как показано выше.
      • mutable.ArrayStack - Класс, реализующий Оптимизированная для LIFO структура данных с использованием массивов. Предположительно, значительно быстрее, чем обычный стек.
      • mutable.Stack , mutable.SynchronizedStack - Классы, реализующие структуру данных, оптимизированную для LIFO.
      • mutable.StackProxy - A Прокси для mutable.Stack ..
      • mutable.Seq
        • mutable.Buffer - последовательность элементов, которая может быть изменена путем добавления, добавления или вставки новые участники.
          • mutable.ArrayBuffer - реализация класса mutable.Buffer с постоянным амортизированным временем для операций добавления, обновления и произвольного доступа. Он имеет несколько специализированных подклассов, таких как NodeBuffer .
          • mutable.BufferProxy , mutable.SynchronizedBuffer .
          • mutable.ListBuffer - буфер с поддержкой списком. Он обеспечивает добавление и начало с постоянным временем, при этом большинство других операций являются линейными.
          • mutable.ObservableBuffer - свойство mixin , которое при смешивании с буфером обеспечивает события уведомления через интерфейсы Publisher .
          • mutable.IndexedSeq - как показано выше.
          • mutable.LinearSeq - как показано выше.
            • BitSet - набор целых чисел, хранящийся в виде битового набора.
              • immutable.BitSet
              • mutable.BitSet
            • SortedSet - набор, элементы которого упорядочены. Конкретная общая реализация для классов с определенной структурой (проходимая, карта и т.д.) выполняется в классах Like. Затем классы, предназначенные для общего использования, переопределяют выбранные методы, которые могут быть оптимизированы.
              • Для чего предназначены сопутствующие методы (например, List.companion)

              Конструктор классов, то есть объект, который знает, как создавать экземпляры этого класса таким образом, который может использоваться такими методами, как map , создается методом в сопутствующем объекте. Итак, чтобы построить объект типа X, мне нужно получить этот конструктор из сопутствующего объекта X. К сожалению, в Scala нет способа перейти от класса X к объекту X. Из-за этого существует метод, определенный в каждом экземпляре X, companion , который возвращает сопутствующий объект класса X.

              Хотя такой метод может иметь некоторое применение в обычных программах, его цель - разрешить повторное использование кода в библиотеке коллекции.

              • Как я узнаю, какие неявные объекты находятся в области видимости в данной точке

              Вы не должен заботиться об этом. Они являются неявными, так что вам не нужно выяснять, как заставить их работать.

              Эти имплициты существуют для того, чтобы позволить методам в коллекциях быть определенными в родительских классах, но все же возвращать коллекцию того же типа. Например, метод map определен в TraversableLike , но если вы использовали в List , вы получите обратно List .

              • Как я узнаю, какие неявные объекты находятся в области видимости в данной точке

              Вы не должны беспокоиться об этом. Они являются неявными, так что вам не нужно выяснять, как заставить их работать.

              Эти имплициты существуют для того, чтобы позволить методам в коллекциях быть определенными в родительских классах, но все же возвращать коллекцию того же типа. Например, метод map определен в TraversableLike , но если вы использовали в List , вы получите обратно List .

              • Как я узнаю, какие неявные объекты находятся в области видимости в данной точке

              Вы не должны беспокоиться об этом. Они являются неявными, поэтому вам не нужно выяснять, как заставить их работать.

              Эти имплициты существуют для того, чтобы можно было определять методы в коллекциях в родительских классах, но при этом возвращать коллекцию того же типа. Например, метод map определен в TraversableLike , но если вы использовали в List , вы получите обратно List .