ImmutableSortedDictionary rango enumeración por clave

11

Estaba leyendo sobre C # 's ImmutableSortedDictionaryen System.Collections.Immutabley pensando acerca de cómo aplicarlo en mi programa. Me gustan bastante los C ++ lower_boundy upper_bound(ver aquí ), y esperaba ver algo parecido para las búsquedas de rango. Sin embargo, métodos similares parecen estar extrañamente ausentes de la documentación . ¿Me estoy perdiendo de algo? ¿O MS realmente proporciona un diccionario ordenado sin acceso eficiente a los rangos ordenados? Eso no parece exactamente algo que uno podría hacer en una IEnumerablede las teclas como decir un método de extensión, por lo que estoy un poco perplejo porque no veo algo proporcionado directamente por la colección.

c# .net algorithm immutability immutable-collections J Trana
fuente
Eric Lippert compartió una implementación inmutable del árbol AVL en 2008. A partir de los comentarios, no creo que haya sido particularmente optimizado para la velocidad o la eficiencia todavía, pero la IBinarySearchTree<K,V>implementación se parece más a lo que esperaría. Me pregunto si alguna vez lo jugó más.
J Trana
La ImmutableList<T>clase también se implementa como un árbol AVL. Del código fuente :/// The root node of the AVL tree that stores this set.
Theodor Zoulias el
¿Sabes si significan que la lista usa un AVL verdadero para implementar la inmutabilidad o si el árbol AVL es inmutable? (Tal vez no importa, ya que no exponen el árbol de todos modos).
J Trana
Aquí están las ventajas de ImmutableList<T>(respaldado por un árbol AVL) sobre ImmutableArray<T>(respaldado por una matriz), de acuerdo con la documentación . Razones para usar la lista inmutable: 1) Actualizar los datos es común o no se espera que el número de elementos sea pequeño. 2) Actualizar la colección es más crítico para el rendimiento que iterar los contenidos.
Theodor Zoulias el
Esto se debe a que al agregar o eliminar un elemento de un gran árbol AVL, puede obtener un nuevo árbol sin destruir el original, compartiendo la mayoría de los nodos y creando solo unos pocos nodos nuevos. ( Estructura de datos persistente - Árboles )
Theodor Zoulias

Respuestas:

9

Es irritante que las colecciones incorporadas disponibles no ofrezcan un conjunto completo de características (como la SortedDictionaryfalta de un BinarySearchmétodo), lo que nos obliga a buscar soluciones de terceros (como la biblioteca C5 ).

En su caso, en lugar de un ImmutableSortedDictionary, probablemente podría usar un ImmutableSortedSet, incrustando los valores en las claves y usando un comparador apropiado. Al menos la API de esta clase contiene las propiedades Miny Max.

Theodor Zoulias
fuente
2
Como nota al margen, otra clase inmutable, la ImmutableList<T>, se implementa internamente como un árbol . Por lo tanto, es 10 veces más lento y asigna 12 veces más memoria que a List<T>. Usar en su ImmutableArray<T>lugar.
Theodor Zoulias el
1
Jeje, ya uso C5 pero estoy buscando ver qué estaba disponible para colecciones inmutables (más allá de las instantáneas). ¡Gracias! Voy a mantener la esperanza de que alguien más haya resuelto esto de alguna forma o forma, pero tendré en cuenta elImmutableSortedSet
J Trana
@TheodorZoulias, ¿qué sentido tiene tener el método BinarySearch en SortedDictionary, cuando el método TryGetValue funciona en log (N)? ver aquí
Giorgi Chkhikvadze
2
@GiorgiChkhikvadze the BinarySearch puede darle el siguiente elemento que es más grande que el elemento que está buscando, en caso de que no se encuentre una coincidencia exacta.
Theodor Zoulias el
1
@GiorgiChkhikvadze Probablemente la mayor diferencia aquí es que el valor de retorno no es solo un valor único en la colección, sino más bien una forma de indexar en la colección de manera eficiente. El método BinarySearch es especial no solo porque encuentra el valor eficientemente sino porque también encuentra un índice incluso en el caso de una falla como señaló Theodor, lo que permite un acceso rápido, por ejemplo, a una matriz. Sin embargo, en el caso de un árbol, un índice entero podría no ser una forma eficiente de acceder a la estructura; C ++ resuelve esto mediante el uso de un objeto iterador (aunque con sus propias complejidades).
J Trana