Nach meiner atemlosen Verwirrung gibt es einige gute Ressourcen, die erklären, wie die neue Scala 2.8- Sammlungsbibliothek strukturiert wurde. Ich bin daran interessiert, Informationen darüber zu finden, wie Folgendes zusammenpasst:
- Die Sammlung Klassen / traits selbst (zB
List
,Iterable
) - Warum die wie Klassen existieren (zB
TraversableLike
) - Was die Begleiter Methoden sind für (zB
List.companion
) - Woher weiß ich, welche
implicit
Objekte zu einem bestimmten Zeitpunkt im Umfang sind?
scala
scala-collections
scala-2.8
oxbow_lakes
quelle
quelle
Antworten:
Vorwort
Es gibt eine 2.8-Sammlung von Martin Odersky, die wahrscheinlich Ihre erste Referenz sein sollte. Es wurde auch durch architektonische Anmerkungen ergänzt , die für diejenigen von besonderem Interesse sein werden, die ihre eigenen Kollektionen entwerfen möchten.
Der Rest dieser Antwort wurde geschrieben, bevor es so etwas gab (tatsächlich bevor 2.8.0 selbst veröffentlicht wurde).
Sie finden ein Papier darüber als Scala SID # 3 . Andere Artikel in diesem Bereich sollten auch für Leute interessant sein, die an den Unterschieden zwischen Scala 2.7 und 2.8 interessiert sind.
Ich werde selektiv aus dem Papier zitieren und einige meiner Gedanken ergänzen. Es gibt auch einige Bilder, die von Matthias auf decodified.com erstellt wurden. Die Original-SVG-Dateien finden Sie hier .
Die Sammlungsklassen / -merkmale selbst
Tatsächlich gibt es drei Hierarchien von Merkmalen für die Sammlungen: eine für veränderbare Sammlungen, eine für unveränderliche Sammlungen und eine, die keine Annahmen über die Sammlungen macht.
Es gibt auch eine Unterscheidung zwischen parallelen, seriellen und möglicherweise parallelen Sammlungen, die mit Scala 2.9 eingeführt wurden. Ich werde im nächsten Abschnitt darüber sprechen. Die in diesem Abschnitt beschriebene Hierarchie bezieht sich ausschließlich auf nicht parallele Sammlungen .
Das folgende Bild zeigt die mit Scala 2.8 eingeführte unspezifische Hierarchie:
Alle gezeigten Elemente sind Merkmale. In den beiden anderen Hierarchien gibt es auch Klassen, die die Merkmale direkt erben, sowie Klassen, die durch implizite Konvertierung in Wrapper-Klassen als zu dieser Hierarchie gehörend angesehen werden können . Die Legende für diese Grafiken finden Sie danach.
Grafik für unveränderliche Hierarchie:
Grafik für veränderbare Hierarchie:
Legende:
Hier ist eine abgekürzte ASCII-Darstellung der Sammlungshierarchie für diejenigen, die die Bilder nicht sehen können.
Traversable | | Iterable | +------------------+--------------------+ Map Set Seq | | | | +----+----+ +-----+------+ Sorted Map SortedSet BitSet Buffer Vector LinearSeq
Parallele Sammlungen
Als Scala 2.9 parallele Kollektionen einführte, bestand eines der Designziele darin, ihre Verwendung so nahtlos wie möglich zu gestalten. Im einfachsten Sinne kann man eine nicht parallele (serielle) Sammlung durch eine parallele ersetzen und sofort von den Vorteilen profitieren.
Da jedoch alle Sammlungen bis dahin Serien waren, von denen viele Algorithmen angenommen und auf der Tatsache beruhte , dass sie waren serial. Parallele Sammlungen, die den Methoden mit solchen Annahmen zugeführt werden, würden fehlschlagen. Aus diesem Grund erfordert die gesamte im vorherigen Abschnitt beschriebene Hierarchie die serielle Verarbeitung .
Zur Unterstützung der parallelen Sammlungen wurden zwei neue Hierarchien erstellt.
Die parallelen Sammlungen Hierarchie hat die gleichen Namen für Züge, aber voraus mit
Par
:ParIterable
,ParSeq
,ParMap
undParSet
. Beachten Sie, dass dies nicht der Fall istParTraversable
, da jede Sammlung, die den parallelen Zugriff unterstützt, das stärkereParIterable
Merkmal unterstützen kann. Einige der spezielleren Merkmale der seriellen Hierarchie sind ebenfalls nicht vorhanden. Diese gesamte Hierarchie befindet sich unter dem Verzeichnisscala.collection.parallel
.Die Klassen, die parallele Sammlungen implementieren, unterscheiden sich ebenfalls mit
ParHashMap
undParHashSet
für veränderbare und unveränderliche parallele SammlungenParRange
sowie für dieParVector
Implementierungimmutable.ParSeq
undParArray
Implementierungmutable.ParSeq
.Eine weitere Hierarchie existiert auch , dass Spiegel die Merkmale von seriellen und parallelen Sammlungen, aber mit einem Präfix
Gen
:GenTraversable
,GenIterable
,GenSeq
,GenMap
undGenSet
. Diese Merkmale sind Eltern sowohl paralleler als auch serieller Sammlungen. Dies bedeutet, dass eine Methode, die aSeq
verwendet, keine parallele Sammlung empfangen kann. EsGenSeq
wird jedoch erwartet, dass eine Methode, die a verwendet, sowohl mit seriellen als auch mit parallelen Sammlungen funktioniert.Angesichts der Struktur dieser Hierarchien war der für Scala 2.8 geschriebene Code vollständig mit Scala 2.9 kompatibel und erforderte serielles Verhalten. Ohne Umschreibung können parallele Sammlungen nicht genutzt werden, die erforderlichen Änderungen sind jedoch sehr gering.
Parallele Sammlungen verwenden
Jede Sammlung kann durch Aufrufen der Methode in eine parallele umgewandelt werden
par
. Ebenso kann jede Sammlung durch Aufrufen der Methode in eine serielle Sammlung konvertiert werdenseq
.Wenn die Sammlung bereits vom angeforderten Typ war (parallel oder seriell), findet keine Konvertierung statt. Wenn man jedoch
seq
eine parallele Sammlung oderpar
eine serielle Sammlung aufruft , wird eine neue Sammlung mit dem angeforderten Merkmal erzeugt.Verwechseln Sie nicht
seq
, was eine Sammlung in eine nicht parallele Sammlung verwandelt, mittoSeq
, was eineSeq
aus den Elementen der Sammlung erstellte Sammlung zurückgibt . Wenn SietoSeq
eine parallele Sammlung aufrufen, wird eineParSeq
, keine serielle Sammlung zurückgegeben.Die Hauptmerkmale
Während es viele implementierende Klassen und Subtraits gibt, gibt es einige grundlegende Merkmale in der Hierarchie, von denen jedes mehr Methoden oder spezifischere Garantien bietet, aber die Anzahl der Klassen reduziert, die sie implementieren könnten.
In den folgenden Unterabschnitten werde ich eine kurze Beschreibung der Hauptmerkmale und der Idee dahinter geben.
Trait TraversableOnce
Dieses Merkmal ähnelt dem
Traversable
unten beschriebenen Merkmal , jedoch mit der Einschränkung, dass Sie es nur einmal verwenden können . Das heißt, alle Methoden, die auf a aufgerufen werden,TraversableOnce
können es unbrauchbar machen.Diese Einschränkung ermöglicht die gemeinsame Nutzung derselben Methoden zwischen den Sammlungen und
Iterator
. Dies ermöglicht es einer Methode, die mit einer,Iterator
aber nichtIterator
spezifischen Methode arbeitet, tatsächlich mit jeder Sammlung und Iteratoren arbeiten zu können, wenn sie zur Annahme umgeschrieben wirdTraversableOnce
.Da
TraversableOnce
Sammlungen und Iteratoren vereinheitlicht werden, werden sie in den vorherigen Diagrammen nicht angezeigt, die sich nur mit Sammlungen befassen.Travers Traversable
An der Spitze der Sammlungshierarchie steht das Merkmal
Traversable
. Seine einzige abstrakte Operation istdef foreach[U](f: Elem => U)
Die Operation soll alle Elemente der Sammlung durchlaufen und die angegebene Operation f auf jedes Element anwenden. Die Anwendung erfolgt nur wegen ihrer Nebenwirkung; Tatsächlich wird jedes Funktionsergebnis von f von foreach verworfen.
Durchquerbare Objekte können endlich oder unendlich sein. Ein Beispiel für ein unendlich durchquerbares Objekt ist der Strom natürlicher Zahlen
Stream.from(0)
. Die MethodehasDefiniteSize
gibt an, ob eine Sammlung möglicherweise unendlich ist. WennhasDefiniteSize
true zurückgegeben wird, ist die Sammlung sicherlich endlich. Wenn false zurückgegeben wird, wurde die Sammlung noch nicht vollständig ausgearbeitet, sodass sie möglicherweise unendlich oder endlich ist.Diese Klasse definiert Methoden, die effizient implementiert werden können
foreach
(über 40 davon).Eigenschaft Iterable
Dieses Merkmal deklariert eine abstrakte Methode
iterator
, die einen Iterator zurückgibt, der alle Elemente der Sammlung nacheinander liefert. Dieforeach
Methode inIterable
ist implementiert in Bezug aufiterator
. UnterklassenIterable
überschreiben häufig foreach mit einer direkten Implementierung für Effizienz.Class
Iterable
fügt auch einige weniger häufig verwendete Methoden hinzuTraversable
, die nur dann effizient implementiert werden können, wenn eineiterator
verfügbar ist. Sie sind unten zusammengefasst.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
Andere Eigenschaften
Nachdem
Iterable
es kommen drei Grundeigenschaften , die sich von ihm erbenSeq
,Set
undMap
. Alle drei haben eineapply
Methode und alle drei implementieren dasPartialFunction
Merkmal, aber die Bedeutung vonapply
ist in jedem Fall unterschiedlich.Ich vertraue darauf , die Bedeutung
Seq
,Set
undMap
ist intuitiv. Danach teilen sich die Klassen in bestimmte Implementierungen auf, die besondere Garantien hinsichtlich der Leistung und der daraus resultierenden Methoden bieten. Ebenfalls erhältlich sind einige Merkmale mit weiteren Verfeinerungen, wieLinearSeq
,IndexedSeq
undSortedSet
.Die folgende Auflistung kann verbessert werden. Hinterlasse einen Kommentar mit Vorschlägen und ich werde ihn beheben.
Basisklassen und Eigenschaften
Traversable
- Grundlegende Sammlungsklasse. Kann nur mit implementiert werdenforeach
.TraversableProxy
- Proxy für aTraversable
. Zeigen Sie einfachself
auf die echte Sammlung.TraversableView
- Ein Traversable mit einigen nicht strengen Methoden.TraversableForwarder
- Leitet die meisten Methoden aufunderlying
, mit der AusnahmetoString
,hashCode
,equals
,stringPrefix
,newBuilder
,view
und alle Anrufe ein neues iterable Objekt der gleichen Art zu schaffen.mutable.Traversable
undimmutable.Traversable
- dasselbe wieTraversable
, aber Einschränkung des Sammlungstyps.Iterable
wieMetaData
.Iterable
- Eine Sammlung, für die eineIterator
(durchiterator
) erstellt werden kann.IterableProxy
,IterableView
,mutable
Undimmutable.Iterable
.Iterator
- Ein Merkmal, das nicht abstammtTraversable
. Definierennext
undhasNext
.CountedIterator
- EineIterator
Definitioncount
, die die bisher gesehenen Elemente zurückgibt.BufferedIterator
- Definierthead
, was das nächste Element zurückgibt, ohne es zu verbrauchen.Iterator
wieSource
.Die Karten
Map
- EinIterable
vonTuple2
, das auch Methoden zum Abrufen eines Werts (des zweiten Elements des Tupels) mit einem Schlüssel (des ersten Elements des Tupels) bereitstellt. Erweitert sichPartialFunction
auch.MapProxy
- AProxy
für aMap
.DefaultMap
- Ein Merkmal, das einige derMap
abstrakten Methoden implementiert .SortedMap
- A,Map
dessen Schlüssel sortiert sind.immutable.SortMap
immutable.TreeMap
- Eine Klasse, die implementiertimmutable.SortedMap
.immutable.Map
immutable.MapProxy
immutable.HashMap
- Eine Klasse, dieimmutable.Map
durch Schlüssel-Hashing implementiert wird.immutable.IntMap
- Eine Klasse, dieimmutable.Map
aufInt
Schlüssel spezialisiert ist . Verwendet einen Baum basierend auf den Binärziffern der Schlüssel.immutable.ListMap
- Eine Klasse, dieimmutable.Map
durch Listen implementiert wird.immutable.LongMap
- Eine Klasse, dieimmutable.Map
aufLong
Schlüssel spezialisiert ist . SieheIntMap
.mutable.Map
mutable.HashMap
- Eine Klasse, diemutable.Map
durch Schlüssel-Hashing implementiert wird.mutable.ImmutableMapAdaptor
- Eine Klasse, die einmutable.Map
aus einem vorhandenen implementiertimmutable.Map
.mutable.LinkedHashMap
-?mutable.ListMap
- Eine Klasse, diemutable.Map
durch Listen implementiert wird.mutable.MultiMap
- Eine Klasse, die mehr als einen bestimmten Wert für jeden Schlüssel akzeptiert.mutable.ObservableMap
- Ein Mixin, das, wenn es mit a gemischt wirdMap
, Ereignisse über einePublisher
Schnittstelle für Beobachter veröffentlicht .mutable.OpenHashMap
- Eine Klasse, die auf einem offenen Hashing-Algorithmus basiert.mutable.SynchronizedMap
- Ein Mixin, das mit a gemischt werden sollteMap
, um eine Version davon mit synchronisierten Methoden bereitzustellen.mutable.MapProxy
.Die Sequenzen
Seq
- Eine Folge von Elementen. Man geht von einer genau definierten Größen- und Elementwiederholung aus. Erweitert sichPartialFunction
auch.IndexedSeq
- Sequenzen, die den Zugriff auf O (1) -Elemente und die Berechnung der O (1) -Länge unterstützen.IndexedSeqView
immutable.PagedSeq
- Eine Implementierung,IndexedSeq
bei der die Elemente bei Bedarf von einer durch den Konstruktor übergebenen Funktion erzeugt werden.immutable.IndexedSeq
immutable.Range
- Eine begrenzte Folge von ganzen Zahlen, die am unteren Ende geschlossen, am oberen Ende offen und mit einem Schritt versehen sind.immutable.Range.Inclusive
- EinRange
geschlossenes auch am oberen Ende.immutable.Range.ByOne
- A,Range
dessen Schritt 1 ist.immutable.NumericRange
- Eine allgemeinere VersionRange
davon funktioniert mit jedemIntegral
.immutable.NumericRange.Inclusive
,immutable.NumericRange.Exclusive
.immutable.WrappedString
,immutable.RichString
- Wrapper, die es ermöglichen, aString
als zu sehenSeq[Char]
, während dieString
Methoden erhalten bleiben. Ich bin mir nicht sicher, was der Unterschied zwischen ihnen ist.mutable.IndexedSeq
mutable.GenericArray
- EineSeq
Array-ähnliche Struktur auf Basis. Beachten Sie, dass die "Klasse"Array
Java istArray
, die eher eine Speichermethode als eine Klasse ist.mutable.ResizableArray
- Interne Klasse, die von Klassen verwendet wird, die auf Arrays mit veränderbarer Größe basieren.mutable.PriorityQueue
,mutable.SynchronizedPriorityQueue
- Klassen, die priorisierte Warteschlangen implementieren - Warteschlangen, in denen die Elemente gemäß einerOrdering
ersten und der Reihenfolge der letzten Warteschlangen aus der Warteschlange entfernt werden.mutable.PriorityQueueProxy
- eine ZusammenfassungProxy
für aPriorityQueue
.LinearSeq
- Ein Merkmal für lineare Sequenzen, mit effizienter ZeitisEmpty
,head
undtail
.immutable.LinearSeq
immutable.List
- Eine unveränderliche, einfach verknüpfte Listenimplementierung.immutable.Stream
- Eine faule Liste. Seine Elemente werden nur bei Bedarf berechnet, aber anschließend gespeichert (gespeichert). Es kann theoretisch unendlich sein.mutable.LinearSeq
mutable.DoublyLinkedList
- Eine Liste mit wandelbarprev
,head
(elem
) undtail
(next
).mutable.LinkedList
- Eine Liste mit veränderlichenhead
(elem
) undtail
(next
).mutable.MutableList
- Eine Klasse, die intern zum Implementieren von Klassen verwendet wird, die auf veränderlichen Listen basieren.mutable.Queue
,mutable.QueueProxy
- Eine für FIFO-Operationen (First-In, First-Out) optimierte Datenstruktur.mutable.QueueProxy
- AProxy
für amutable.Queue
.SeqProxy
,SeqView
,SeqForwarder
immutable.Seq
immutable.Queue
- Eine Klasse, die eine FIFO-optimierte Datenstruktur (First-In, First-Out) implementiert. Es gibt keine gemeinsame Oberklasse von beidenmutable
undimmutable
Warteschlangen.immutable.Stack
- Eine Klasse, die eine LIFO-optimierte Datenstruktur (Last-In, First-Out) implementiert. Es gibt keine gemeinsame Oberklasse beidermutable
immutable
Stapel.immutable.Vector
-?scala.xml.NodeSeq
- Eine spezielle XML-Klasse, die erweitert wirdimmutable.Seq
.immutable.IndexedSeq
- Wie oben gesehen.immutable.LinearSeq
- Wie oben gesehen.mutable.ArrayStack
- Eine Klasse, die eine LIFO-optimierte Datenstruktur mithilfe von Arrays implementiert. Angeblich deutlich schneller als ein normaler Stack.mutable.Stack
,mutable.SynchronizedStack
- Klassen, die eine LIFO-optimierte Datenstruktur implementieren.mutable.StackProxy
- AProxy
für einemutable.Stack
..mutable.Seq
mutable.Buffer
- Reihenfolge der Elemente, die durch Anhängen, Voranstellen oder Einfügen neuer Elemente geändert werden können.mutable.ArrayBuffer
- Eine Implementierung dermutable.Buffer
Klasse mit konstanter Amortisationszeit für die Anhänge-, Aktualisierungs- und Direktzugriffsoperationen. Es hat einige spezialisierte Unterklassen, wie zNodeBuffer
.mutable.BufferProxy
,mutable.SynchronizedBuffer
.mutable.ListBuffer
- Ein Puffer, der von einer Liste unterstützt wird. Es bietet eine konstante Zeit zum Anhängen und Voranstellen, wobei die meisten anderen Operationen linear sind.mutable.ObservableBuffer
- Ein Mixin- Merkmal, das beim Mischen mit aBuffer
Benachrichtigungsereignisse über einePublisher
Schnittstelle bereitstellt.mutable.IndexedSeq
- Wie oben gesehen.mutable.LinearSeq
- Wie oben gesehen.Die Sätze
Set
- Eine Menge ist eine Sammlung, die höchstens eines Objekts enthält.BitSet
- Eine Reihe von Ganzzahlen, die als Bitset gespeichert sind.immutable.BitSet
mutable.BitSet
SortedSet
- Eine Menge, deren Elemente geordnet sind.immutable.SortedSet
immutable.TreeSet
- Eine Implementierung einesSortedSet
auf einem Baum basierenden.SetProxy
- AProxy
für aSet
.immutable.Set
immutable.HashSet
- Eine Implementierung vonSet
basierend auf Element-Hashing.immutable.ListSet
- Eine Implementierung vonSet
basierend auf Listen.immutable.SetProxy
- AProxy
für einen unveränderlichenSet
.mutable.Set
mutable.HashSet
- Eine Implementierung vonSet
basierend auf Element-Hashing.mutable.ImmutableSetAdaptor
- Eine Klasse, die eine veränderbareSet
von einer unveränderlichen implementiertSet
.LinkedHashSet
- Eine Implementierung vonSet
basierend auf Listen.ObservableSet
- Ein Mixin- Merkmal, das, wenn es mit a gemischt wirdSet
, Benachrichtigungsereignisse über einePublisher
Schnittstelle bereitstellt.SetProxy
- AProxy
für aSet
.SynchronizedSet
- Ein Mixin- Merkmal, das, wenn es mit a gemischt wirdSet
, Benachrichtigungsereignisse über einePublisher
Schnittstelle bereitstellt.Dies wurde durchgeführt, um eine maximale Wiederverwendung von Code zu erreichen. Die konkrete generische Implementierung für Klassen mit einer bestimmten Struktur (eine Traversable, eine Map usw.) erfolgt in den Like-Klassen. Die für den allgemeinen Verbrauch bestimmten Klassen überschreiben dann ausgewählte Methoden, die optimiert werden können.
Der Builder für die Klassen, dh das Objekt, das weiß, wie Instanzen dieser Klasse auf eine Weise erstellt werden, die von Methoden wie verwendet werden kann
map
, wird von einer Methode im Begleitobjekt erstellt. Um ein Objekt vom Typ X zu erstellen, muss ich diesen Builder aus dem Begleitobjekt von X abrufen. Leider gibt es in Scala keine Möglichkeit, von Klasse X zu Objekt X zu gelangen. Aus diesem Grund gibt es eine Eine in jeder Instanz von X definierte Methodecompanion
, die das Begleitobjekt der Klasse X zurückgibt.Während eine solche Methode in normalen Programmen möglicherweise verwendet wird, besteht ihr Ziel darin, die Wiederverwendung von Code in der Sammlungsbibliothek zu ermöglichen.
Das soll dich nicht interessieren. Sie sind genau implizit, damit Sie nicht herausfinden müssen, wie es funktioniert.
Diese Implikationen bestehen darin, dass die Methoden für die Sammlungen für übergeordnete Klassen definiert werden können, aber dennoch eine Sammlung desselben Typs zurückgegeben werden. Zum Beispiel ist die
map
Methode für definiertTraversableLike
, aber wenn Sie für eine verwendet haben, erhaltenList
Sie eineList
Rückerstattung.quelle