Quelles classes de structures de données peuvent être rendues persistantes?

Les structures de données persistantes sont des structures de données immuables. Les opérations sur eux renvoient une nouvelle "copie" de la structure de données, mais modifiée par l'opération; l'ancienne structure de données reste cependant inchangée. L'efficacité est généralement obtenue en partageant certaines des données sous-jacentes et en évitant la copie complète de la structure des données.

Des questions:

• Y a-t-il des résultats concernant les classes de structures de données qui peuvent être rendues persistantes (tout en conservant les complexités identiques ou très similaires)?

• Toutes les structures de données peuvent- elles être rendues persistantes (tout en conservant des complexités identiques ou très similaires)?

• Existe-t-il des structures de données qui ne peuvent pas être rendues persistantes (tout en conservant des complexités identiques ou très similaires)?

Résultat positif: la persistance ne coûte pas trop cher. On peut montrer que chaque structure de données peut être rendue entièrement persistante avec au plus un ralentissement .$O(\lg n)$

Preuve: vous pouvez prendre un tableau et le rendre persistant en utilisant des structures de données standard (par exemple, un arbre binaire équilibré; voir la fin de cette réponse pour un peu plus de détails). Cela entraîne un ralentissement : chaque accès au tableau prend du temps O ( lg n ) avec la structure de données persistante, au lieu du temps O ( 1 ) pour le tableau non persistant. Prenons maintenant tout algorithme impératif dont le temps d'exécution dans le modèle RAM est O ( f ( n ) ) , où n désigne la quantité de mémoire utilisée. Représente toute la mémoire comme un grand tableau (avec$O(\lg n)$$O(\lg n)$$O(1)$$O(f(n))$$n$ éléments), et le rendre persistant à l'aide d'une carte persistante. Chaque étape de l'algorithme impératif entraîne au maximum unralentissement O ( lg n ) , donc le temps total de fonctionnement est O ( f ( n ) lg n ) .$n$$O(\lg n)$$O(f(n) \lg n)$

Apparemment, il est possible de faire un peu mieux: apparemment, on peut réduire le facteur de ralentissement à (temps amorti attendu), en utilisant les techniques du document Demaine cité ci-dessous - mais je ne connais pas les détails de ce travail, donc je ne peux pas en garantir moi-même. Merci à jbapple pour cette observation.$O(\lg \lg n)$

Résultat négatif: vous ne pouvez pas éviter un certain ralentissement, pour certaines structures de données. Pour répondre à votre troisième question, il existe des structures de données où l'on sait que les rendre persistantes introduit un certain ralentissement.

$n$$O(1)$$O(1)$$\Omega(\lg \lg n)$

• Essais persistants pour un contrôle de version efficace . Erik D. Demaine, Stefan Langerman, Eric Price. Algorithmica, volume 57, numéro 3, 2010, pages 462–483.

La borne inférieure est attribuée à Mihai Patrascu, mais il n'y a aucune référence à une source qui donne les détails de la preuve de cette borne inférieure affirmée.

$O(1)$

Il existe également une forte connexion avec les langages de programmation fonctionnels. En particulier, chaque structure de données qui peut être implémentée de manière purement fonctionnelle (sans mutations) est déjà une structure de données persistante. (L'inverse n'est pas nécessairement le cas, hélas.) Si vous voulez plisser les yeux, vous pouvez prendre cela comme une sorte de théorème de classification partielle faible: s'il est implémentable dans un langage de programmation purement fonctionnel avec les mêmes limites de temps que dans un langage impératif, il existe alors une structure de données persistante avec les mêmes limites temporelles que celle non persistante. Je me rends compte que ce n'est probablement pas ce que vous cherchiez - c'est surtout juste une reformulation triviale de la situation.

$O(\lg n)$

$\ell$$d$$d$

$n$$O(\lg n)$$O(\lg n)$$O(\lg n)$

Vous pouvez trouver plus d'explications, avec de jolies images, sur les ressources suivantes:

• Lisez les sections intitulées "Arbres de recherche binaires" et "Structures à accès aléatoire" (en particulier, la méthode de l'arborescence) sur http://toves.org/books/persist/index.html .

• Ou lisez http://netcode.ru/dotnet/?artID=6592#BinaryTrees et certaines des sections suivantes.

• Ou, lisez les sections intitulées "Structures de données fonctionnelles" et "Copie de chemin" (à partir de la page 4) du document Demaine cité ci-dessus: http://erikdemaine.org/papers/ConfluentTries_Algorithmica/paper.pdf

Cela vous donnera l'idée principale. Il y a des détails supplémentaires à prendre en charge, mais les détails sont hors de portée pour cette question. Heureusement, tout cela est standard et il existe de nombreuses informations disponibles dans la littérature sur la façon de construire de telles structures de données. N'hésitez pas à poser une question distincte si les ressources ci-dessus ne suffisent pas et que vous souhaitez plus d'informations sur les détails de la construction d'une structure de données de tableau persistante.