Ich versuche eine zu machenSeil Datenstruktur. Es ist eine Art Binärbaum, d. H. Eine rekursive Datenstruktur.

Der Zweck eines Seils ist, dass das Spalten und Verketten sein sollteschnell, was bedeutetSie vermeiden, ganze Seile zu kopieren.
So sollte zum Beispiel ein Benutzer in der Lage sein zu sagenrope1 + rope2 und erwarte ein Ergebnis in ~ logarithmischer Zeit.

Dies stellt jedoch ein Problem dar:
Wenn ein Seil geändert wird, werden auch seine Eltern indirekt geändert.
Denn mein Ziel ist es zu machenrope Ein Drop-In-Ersatz fürstring, das ist nicht akzeptabel.

Meine Lösung lautet: Wann immer es gibtirgendein Art der Änderung an aropeWürde ich eine erstellenNeu Knoten, mit einer kleinen Änderung, die alten bleiben unverändert.

Theoretisch würde das ziemlich gut funktionieren.

In der Praxis handelt es sich jedoch um eine Heap-Zuordnungfür (fast?) jede Änderung der Saiten.
Sogar eine Änderung um ein Zeichen würde zu einem neuen Heap-Objekt führen, das nicht nur für sich genommen langsam ist, sondern auch die Speicherlokalität erheblich verringert, was sich sehr negativ auf die Leistung auswirkt.

Wie soll ich dieses Problem lösen?