Rendimiento de estructuras de datos inmutables

No tienes que recrear todo el árbol. Muchas de las ramas permanecerán iguales y pueden ser "reutilizadas". Como un ejemplo simple, si el nuevo nodo necesita ser agregado a una hoja en el árbol actual, entonces solo los padres de ese nodo necesitan ser clonados y dar nuevas ramas.

Como otros señalaron, no tienes que volver a crear toda la estructura de datos. Solo tienes que recrear las partes que han cambiado y hacer referencia a los subárboles existentes que permanecieron igual. Gracias a la inmutabilidad de la estructura de datos, puede reutilizar subárboles, por lo que casi nunca se necesita copiar todo. De hecho, si necesita clonar una estructura de datos mutable rara vez, podría tener un impacto mucho mayor.

En particular, para los árboles balanceados (como los árboles rojo-negro) esto da usted:

• O (log N) tiempo de agregar / eliminar elementos del conjunto (igual que la implementación mutable)
• O (log N) espacio (nuevas asignaciones) al agregar / eliminar elementos(mutable tendría O (1))

Esto puede ser, por supuesto, demasiada sobrecarga para algunas aplicaciones, pero en realidad no es tan malo. Además, la asignación en. NET garbage collector es muy rápida (creo, esencialmente O(1)), así que esto no es realmente un problema. Más asignación significa que GC necesita ejecutarse con más frecuencia, pero esto tampoco es tan crítico como puede sonar - las computadoras tienen bastante memoria en estos días. El. NET 4.0 realmente ayuda en muchos casos (ver también la respuesta de Jon Harrop aquí)

Como otros han dicho, una estructura de datos inmutable no tiene que ser completamente recreada, ya que puede reutilizar partes antiguas de sí misma. Puede hacer esto porque las partes antiguas son inmutables y se garantiza que los datos no cambiarán.

Tengo un ejemplo del mundo real de rendimiento inmutable. Hice algunas pruebas con un árbol inmutable Rojo Negro que hice en F# y solo funciona 3 veces más lento que std::sort en c++. Que creo que es muy rápido teniendo en cuenta que no fue diseñado específicamente para clasificar.

Las limitaciones de la semántica del lenguaje solo se aplican al código fuente en el lenguaje. La implementación(compilador, intérprete, entorno de tiempo de ejecución, etc.) es libre de hacer lo que quiera para el mejor rendimiento, siempre y cuando mantenga el mismo comportamiento. Esto es cierto para la mayoría de los idiomas.

Editar:

Se pueden hacer varias optimizaciones incluyendo el intercambio de datos (precisamente porque los datos son inmutables), usando mutabilidad entre bastidores, optimizando llamadas de cola (ya que FP usa un mucha recursión), y otros.

Véase

Programación funcional: eficiencia de la estructura de datos inmutable

(especialmente mi respuesta que apunta a la charla de Rich Hickey) por la evidencia convincente 'general' de que sí, las estructuras inmutables también pueden ser muy eficientes.

En cuanto a lo bien que esto es cierto en el caso específico de F# Set, bueno, tal vez solo moderadamente hoy. Sería genial utilizar una estructura subyacente más eficiente (en términos pragmáticos; en términos teóricos, por supuesto, todo is O (logN) (que en términos prácticos es O(1))).

Simplemente un Conjunto es una entidad de almacenamiento basada en nodos. En el caso de un Conjunto, puede implementarlo como un árbol en el que no está recreando todos los bordes y los nodos cuando "agrega" un elemento a la siguiente versión del Conjunto, sino que solo está creando un nuevo conjunto de bordes. Puede hacer esto porque los nodos en sí nunca cambiarán, ni tampoco los objetos que se mantienen dentro de ellos.

El beneficio real se encuentra dentro de aplicaciones de un solo subproceso, sino más bien en aplicaciones multiproceso. Las estructuras de datos inmutables eliminan la necesidad de mecanismos de bloqueo. Si nunca van a cambiar, no tienes que preocuparte por el estado.

No estoy seguro de cómo se implementa esto en el lenguaje, pero las estructuras de datos podrían percibirse como inmutables para el programador, pero optimizadas entre bastidores.

Por ejemplo, tengo una lista a=[1,2,3,4,5]. I append 6. b=[a [6]] y ambos pueden ser inmutables. No se pierde ningún rendimiento al hacer esto, y es más rápido que copiar los valores.

Entonces, déjame preguntarte, porque no lo sé, ¿por qué sería más lento hacer las cosas como inmutables? En el caso del árbol, yo veo tu punto. Supongo que tendría que recrear nodos por encima del nodo actual, pero no por debajo (suponiendo que tengamos punteros hijos y no punteros padres).