Ich suche nach einer dauerhaften Datenstruktur ähnlich dem Array (aber unveränderlich), die schnelle Indizierungs-, Anhänge-, Voranstellungs- und Iterationsoperationen (gute Lokalität) ermöglicht.
Clojure bietet dauerhaften Vektor, ist jedoch nur zum schnellen Anhängen geeignet. Scalas Vektor hat effektiv ein zeitlich konstantes Anhängen und Voranstellen, aber ich kann nicht verstehen, wie es implementiert ist, da es auf derselben Datenstruktur (Bitmap-Vektor-Trie) wie der Clojure-Vektor und, wie ich verstehe, auf Bit-Mapping-Vektor-Trie basiert kann ohne schnelle Tricks nicht schnell voranstellen.
Ich bin nicht an einer gebrauchsfertigen Implementierung interessiert, sondern an einer Beschreibung, wie eine solche Datenstruktur selbst implementiert werden kann.
Ich habe eine Implementierung einer solchen Datenstruktur in meinem Artikel über den inkrementellen Abgleich regulärer Ausdrücke beschrieben - siehe http://jkff.info/articles/ire/#ropes-strings-with-fast-concatenation und den Text unter und über diesem Abschnitt .
Es ist eine Vielzahl von Bäumen mit konstanter Höhe (wie B-Bäume oder 2-3 Bäume). Grundsätzlich handelt es sich um einen (2,3) -Baum, dessen Blätter (N, 2N-1) -Arrays sind, um einen Overhead pro Element zu vermeiden. (Ein (N, 2N-1) -Array ist ein Array, dessen Längen im Bereich N..2N-1 liegen.) Größeres N führt zu einem geringeren Overhead, erhöht jedoch linear die Komplexität der Aufteilung und Verkettung. Operationen wie Indizieren, Teilen und Verketten sind der Arbeitsweise in 2-3 Bäumen sehr ähnlich und verallgemeinern sich auf Blattebene auf (N, 2N-1).
quelle