Strukturelle Freigabe in Scala List ist einfach und leicht zu verstehen. Aber Scala Vector ist eine kompliziertere Datenstruktur als eine Liste. Wie wird das strukturelle Teilen in Scala Vector erreicht?Strukturelle Freigabe in Scala Vektor
Vektor ist im Grunde ein Baum (trie) mit 32-breit auf jeder Ebene Verzweigung. Wenn Sie ein Foto von, sagen wir, 3000 Elemente und Sie möchten Indexelement 2045, zum Beispiel, die zu 100000010101 binär umwandelt, wird es in 5-Bit-Blöcke zerlegen als Indizes in den Baum zu verwenden: 10 (dh 2) in der ersten Filiale dann 00000 (dh 0) in der nächsten, und schließlich (dh 21) in der Endstation, und dann gibt es die Daten.
Angesichts dieser Struktur ist es einfach zu sehen, wie man Dinge strukturell teilt: Sie können beliebige Unterbäume teilen, die nicht geändert werden. Wenn Sie also einen neuen Vektor mit einem anderen Element 2045 erstellen, müssen Sie nicht alle 3000 Elemente ändern, sondern "nur" drei Arrays der Größe 32 neu erstellen: Das Terminal 1 wird durch eine Kopie ersetzt, wobei das Element 21 aktualisiert wird. dann muss sein Elternteil durch eine Kopie mit diesem neuen Kind im Index 0 ersetzt werden; dann muss sein Elternteil durch den korrekten Unterbaum in Index 2 ersetzt werden.
Nun, das bietet ziemlich viel strukturelles Teilen, solange Sie weit mehr als 32 Elemente in Ihrem Vektor haben, aber es ist immer noch ein ziemlich großer Overhead . Aus diesem Grund sind Zusätze am Ende des Vektors speziell angeordnet, so dass Sie einfach zum bestehenden Array hinzufügen. Die alten Vektoren zeigen immer noch auf dieses Array, aber sie denken, dass das Ende früher ist (und dieser Teil ist unverändert), also klappt es in Ordnung.
Es gibt ein komplexeres, aber ähnliches Schema, um die Addition an der Vorderseite eines Vektors auf ähnliche Weise zu ermöglichen (im Prinzip durch Leerstellen an der Vorderseite und Verfolgung des Punktes über Indizes und Offsets zusätzlich zum Indexierungsschema)).
Der Trick, wie implementiert, funktioniert nicht, um abwechselnde Hinzufügung zu sowohl Vorder- als auch Rückseite zu erlauben, so dort Sie die Bäume jede Ergänzung effektiv wieder aufbauen. Es wäre möglich, eine Version mit noch besserer struktureller Freigabe zu erstellen, aber es wäre wahrscheinlich ein bisschen langsamer, darauf zuzugreifen.
Große Frage! –