ImmutableSortedDictionary, énumération par clé

11

Je lisais à propos de C # 's ImmutableSortedDictionarydans System.Collections.Immutableet la réflexion sur la façon de l' appliquer dans mon programme. J'aime assez C ++ lower_boundet upper_bound(voir ici ), et je m'attendais plutôt à voir quelque chose du genre pour les recherches de plage. Cependant, des méthodes similaires semblent étrangement absentes de la documentation . Suis-je en train de manquer quelque chose? Ou MS fournit-il vraiment un dictionnaire trié sans accès efficace aux plages triées? Cela ne ressemble pas exactement à quelque chose que l'on pourrait faire sur l'une IEnumerabledes clés comme une méthode d'extension, donc je suis un peu perplexe de ne pas voir quelque chose fourni directement par la collection.

c# .net algorithm immutability immutable-collections J Trana
la source
Eric Lippert a partagé une implémentation d'arbre AVL immuable en 2008. D'après les commentaires, je ne pense pas qu'elle ait été particulièrement optimisée pour la vitesse ou l'efficacité, mais la IBinarySearchTree<K,V>mise en œuvre semble plus proche de ce à quoi je m'attendais. Je me demande s'il a jamais bricolé dessus?
J Trana
La ImmutableList<T>classe est également implémentée comme une arborescence AVL. Du code source :/// The root node of the AVL tree that stores this set.
Theodor Zoulias
Savez-vous s'ils signifient que la liste utilise un AVL true pour implémenter l'immuabilité ou si l'arborescence AVL elle-même est immuable? (Peut-être que cela n'a pas d'importance car ils n'exposent pas l'arbre de toute façon).
J Trana
Voici les avantages de ImmutableList<T>(soutenu par une arborescence AVL) par rapport à ImmutableArray<T>(soutenu par un tableau), selon la documentation . Raisons d'utiliser une liste immuable: 1) La mise à jour des données est courante ou le nombre d'éléments ne devrait pas être faible. 2) La mise à jour de la collection est plus critique en termes de performances que l'itération du contenu.
Theodor Zoulias
En effet, lors de l'ajout ou de la suppression d'un élément d'une grande arborescence AVL, vous pouvez obtenir une nouvelle arborescence sans détruire celle d'origine, en partageant la plupart des nœuds et en ne créant que quelques nouveaux nœuds. ( Structure de données persistante - Arbres )
Theodor Zoulias

Réponses:

9

Il est irritant de constater que les collections intégrées disponibles n'offrent pas un ensemble complet de fonctionnalités (comme l' SortedDictionaryabsence de BinarySearchméthode), ce qui nous oblige à rechercher des solutions tierces (comme la bibliothèque C5 ).

Dans votre cas, au lieu d'un, ImmutableSortedDictionaryvous pouvez probablement utiliser un ImmutableSortedSet, en incorporant les valeurs dans les clés et en utilisant un comparateur approprié. Au moins, l'API de cette classe contient les propriétés Minet Max.

Theodor Zoulias
la source
2
En remarque, une autre classe immuable, la ImmutableList<T>, est implémentée en interne sous forme d'arbre . Il est donc 10 fois plus lent et alloue 12 fois plus de mémoire qu'un a List<T>. Utilisez ImmutableArray<T>plutôt.
Theodor Zoulias
1
Hehe, j'utilise déjà C5 mais cherche à voir ce qui était disponible pour les collections immuables (au-delà des instantanés). Merci! Je vais espérer que quelqu'un d'autre a résolu cela d'une manière ou d'une autre, mais je garderai à l'esprit leImmutableSortedSet
J Trana
@TheodorZoulias à quoi sert la méthode BinarySearch dans SortedDictionary, lorsque la méthode TryGetValue fonctionne dans le journal (N)? voir ici
Giorgi Chkhikvadze
2
@GiorgiChkhikvadze le BinarySearch peut vous donner l'élément suivant qui est plus grand que l'élément que vous recherchez, au cas où une correspondance exacte ne serait pas trouvée.
Theodor Zoulias
1
@GiorgiChkhikvadze La plus grande différence ici est probablement que la valeur de retour n'est pas seulement une valeur unique dans la collection, mais plutôt un moyen d'indexer efficacement dans la collection. La méthode BinarySearch est spéciale non seulement parce qu'elle trouve la valeur efficacement mais aussi parce qu'elle trouve un index même en cas de manque comme l'a souligné Theodor - ce qui permet un accès rapide, par exemple dans un tableau. Cependant, dans le cas d'un arbre, un index entier peut ne pas être un moyen efficace d'accéder à la structure; C ++ résout ce problème en utilisant un objet itérateur (quoique avec ses propres complexités).
J Trana