Performance des structures de données immuables

Question

Je ne comprends pas comment peut quelque chose comme un être immuable et ont encore une performance acceptable.

De ce que j'ai lu dans F# Définit utiliser à l'interne Rouge Noir des Arbres que leur mise en œuvre. Si chaque fois que l'on veut ajouter quelque chose de nouveau Rouge d'un Arbre Noir, nous avons essentiellement de recréer, comment peut-il avoir toujours de bonnes performances? Ce qui me manque ici?

Même si je suis demander ce, pour F#'s Ensembles, je pense que c'est comme pertinent dans toute autre langue qui possède ou utilise des données immuables structures.

Merci

Answer 1

Presque tous immuable collections sont une certaine forme d'équilibre de l'arbre. Pour créer une nouvelle arborescence, vous devez réaffecter les nœuds sur le chemin du changement (insertion, suppression, mise à jour "update") à la racine. Tant que l'arbre est équilibré, cela prend du temps logarithmique. Si vous avez quelque chose comme un arbre 2-3-4 (semblables à des arbres rouge-noir) avec outdegree trois, vous pouvez gérer un million d'éléments à l'aide de seulement 10 allocations.

Et dans les langues où les structures de données devraient être pur, ils font en sorte que l'allocation est rapide. L'allocation d'un quatre-nœud d'élément va coûter de comparer, d'un échelon, et quatre magasins. Et dans de nombreux cas, vous pouvez amortir le coût d'une comparaison sur plusieurs allocations.

Si vous voulez en savoir plus sur la façon dont ces structures de travail, une excellente source est Purement Fonctionnelle des Structures de Données par Chris Okasaki.

Answer 2

Vous n'êtes pas obligé de recréer tout l'arbre. Beaucoup de branches resteront les mêmes et pourront être «réutilisées». À titre d’exemple simple, si le nouveau nœud doit être ajouté à une feuille de l’arborescence en cours, seuls les parents de ce nœud doivent être clonés et se voir attribuer de nouvelles branches.

Answer 3

Comme d'autres l'ont souligné, vous n'avez pas à re-créer l'ensemble de la structure de données. Vous avez juste à re-créer des pièces qui ont changé de référence et des sous-arbres qui sont restés les mêmes. Grâce à l'immutabilité de la structure de données, vous pouvez réutiliser les sous-arbres, donc la copie de tout ce qui n'est presque jamais nécessaire. En fait, si vous avez besoin de cloner une structure de données mutable rarement, il pourrait avoir beaucoup plus d'impact.

En particulier, pour un ballanced arbres (comme les arbres rouge-noir) cela vous donne:

• O(log N) le temps d'ajouter/supprimer les éléments de l'ensemble (le même que mutable mise en œuvre)
• O(log N) de l'espace (nouvelles affectations) lors de l'ajout/suppression d'éléments (mutable aurait O(1))

Cela peut être bien sûr trop de frais généraux pour certaines applications, mais en fait elle n'est pas si mauvais que ça. En outre, l'allocation .NET garbage collector est très rapide (je pense, essentiellement en O(1)), donc ce n'est pas vraiment un problème. Plus d'allocation des moyens que GC a besoin pour fonctionner de plus en plus fréquemment, mais ce n'est pas aussi critique que cela puisse paraître - les ordinateurs ont beaucoup de mémoire de ces jours. L' .NET 4.0, permet en fait, dans de nombreux cas (voir aussi Jon Harrop la réponse ici)

Answer 4

Comme d'autres l'ont déclaré immuable structure de données n'a pas à être complètement recréée car il peut réutiliser les anciennes parties de lui-même. Vous pouvez faire cela, car les parties les plus anciennes sont immuables et les données est garanti de ne pas changer.

J'ai un exemple réel de immuable de la performance. J'ai fait quelques tests avec une immuable Rouge Noir de l'arbre que j'ai fait en F#, et il effectue 3 fois plus lent que std::sort en c++. Je pense que c'est vraiment rapide, considérant qu'il n'a pas été conçu spécifiquement pour le tri.

Answer 5

Les limites du langage sémantique s'applique uniquement pour le code source dans la langue. La mise en œuvre (compilateur, interpréteur, l'environnement d'exécution, etc.) est libre de faire ce qu'il veut pour la meilleure performance, aussi longtemps que il garde le même comportement. Cela est vrai pour la plupart des langues.

Edit:

Plusieurs optimisations peuvent être faites, y compris le partage des données (précisément parce que les données sont immuables), à l'aide de la mutabilité derrière les coulisses, l'optimisation de la queue des appels (depuis FP utilise beaucoup de récursivité), et d'autres.