Mise en œuvre de structure de données immuable (persistante) de type tableau avec indexation rapide, ajout, pré-ajout, itération

Je recherche une structure de données persistante similaire à un tableau (mais immuable), permettant des opérations d'indexation, d'ajout, de pré-ajout et d'itération rapides (bonne localité).

Clojure fournit un vecteur persistant, mais ce n'est que pour un ajout rapide. Le vecteur de Scala a effectivement un ajout et un pré-ajout à temps constant, mais je ne peux pas comprendre comment il est implémenté, car il est basé sur la même structure de données (tri vectoriel bit-mappé) que le vecteur Clojure et, si je comprends bien, le trie vectoriel bit-mappé ne peut pas avoir un préfixe rapide sans quelques astuces.

Je ne suis pas intéressé par l'implémentation prête à l'emploi, mais par une description de la façon d'implémenter une telle structure de données moi-même.

Le candidat évident est un arbre binaire équilibré persistant . Toutes les opérations que vous avez répertoriées peuvent être effectuées en temps ou O ( lg n ) , en utilisant la copie de chemin . Pour plus de détails sur la façon d'atteindre ce runtime, voir le livre de Chris Okasaki référencé ci-dessous ou ma réponse ici .$O(1)$$O(\lg n)$

Bien entendu, en variante, chaque feuille d'un tel arbre pourrait elle-même contenir un tableau immuable (une séquence de valeurs consécutives). Cela rend la mise à jour d'une valeur moins efficace, mais cela pourrait bien fonctionner pour votre situation, si vous n'avez jamais l'intention de modifier une valeur existante, il suffit d'ajouter et de pré-ajouter. De cette façon, votre vecteur est représenté comme une séquence de séquences immuables, représenté comme un arbre binaire équilibré avec des tableaux immuables dans les feuilles. Cela permet une indexation rapide (logarithmique du nombre de feuilles), un ajout et un ajout rapides et une itération rapide. La complexité asymptotique du pire des cas n'est pas meilleure, mais les performances dans la pratique pourraient être nettement meilleures.

La référence standard est le livre de Chris Okasaki de 1998 "Structures de données purement fonctionnelles".
Voir également

• Quelles classes de structures de données peuvent être rendues persistantes?
• Quoi de neuf dans les structures de données purement fonctionnelles depuis Okasaki?
• Quelles sont les questions en suspens dans les structures de données purement fonctionnelles?
• Dix ans de structures de données purement fonctionnelles

J'ai décrit une implémentation d'une telle structure de données dans mon article sur la correspondance d'expression régulière incrémentielle - voir http://jkff.info/articles/ire/#ropes-strings-with-fast-concatenation et le texte ci-dessous et au-dessus de cette section .

C'est une variété d'arbre à hauteur constante (comme les arbres B ou 2-3 arbres). Fondamentalement, c'est un arbre (2,3), dont les feuilles sont des tableaux (N, 2N-1), afin d'éviter les frais généraux par élément. (Un tableau (N, 2N-1) est un tableau dont les longueurs dans la plage N..2N-1.) Un N plus grand vous donne un surdébit plus petit mais augmente linéairement la complexité du fractionnement et de la concaténation. Les opérations telles que l'indexation, le fractionnement et la concaténation sont très similaires à la façon dont elles fonctionnent dans 2-3 arbres, généralisant à (N, 2N-1) au niveau de la feuille.