.net - son - Rendimiento de estructuras de datos inmutables
principios inmutables (8)
No entiendo cómo puede algo como un conjunto ser inmutable y aún tener un rendimiento aceptable.
De lo que he leído en F # Sets internamente uso Red Black Trees como su implementación. Si cada vez que queremos agregar algo nuevo a un árbol rojo negro tenemos que recrearlo básicamente, ¿cómo puede tener un buen rendimiento? ¿Que me estoy perdiendo aqui?
Aunque estoy pidiendo esto para Sets de F #, creo que esto es tan relevante en cualquier otro idioma que tenga o use estructuras de datos inmutables.
Gracias
Casi todas las colecciones inmutables son alguna forma de árbol equilibrado. Para crear un nuevo árbol, debe reasignar nodos en la ruta desde el cambio (insertar, eliminar, "actualizar") a la raíz. Siempre que el árbol esté equilibrado, esto requiere tiempo logarítmico. Si tiene algo así como un árbol 2-3-4 (similar a los árboles rojo-negro) con un resultado esperado de tres grados, puede manejar un millón de elementos usando solo 10 asignaciones.
Y en los idiomas donde se espera que las estructuras de datos sean puras, se aseguran de que la asignación sea rápida. La asignación de un nodo de cuatro elementos costará una comparación, un incremento y cuatro tiendas. Y en muchos casos puede amortizar el costo de una comparación en varias asignaciones.
Si desea saber más sobre cómo funcionan estas estructuras, una fuente excelente es Purely Functional Data Structures de Chris Okasaki.
Como otros han declarado, una estructura de datos inmutable no tiene que ser completamente recreada ya que puede reutilizar partes viejas de sí mismo. Puede hacerlo porque las piezas antiguas son inmutables y se garantiza que los datos no cambian.
Tengo un ejemplo del mundo real de rendimiento inmutable. Hice algunas pruebas con un árbol inmutable de color rojo y negro que hice en F # y solo funciona 3 veces más lento que std :: sort en c ++. Lo cual creo que es realmente rápido teniendo en cuenta que no fue diseñado específicamente para la clasificación.
Como otros señalaron, no es necesario volver a crear toda la estructura de datos. Solo tiene que volver a crear las partes que han cambiado y hacer referencia a los subárboles existentes que permanecieron iguales. 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 necesitara clonar una estructura de datos mutable en raras ocasiones, podría tener un impacto mucho mayor.
En particular, para árboles balanceados (como árboles rojo-negro) esto le da:
- O (log N) tiempo de agregar / eliminar elementos del conjunto (igual que la implementación mutable)
- Espacio O (log N) (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 el recolector de basura .NET es muy rápida (creo, esencialmente O (1) ), así que esto no es realmente un problema. Una mayor asignación significa que GC necesita ejecutarse con mayor frecuencia, pero esto tampoco es tan crítico como podría parecer: 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í )
Las limitaciones de la semántica del lenguaje solo se aplican al código fuente en el idioma. La implementación (compilador, intérprete, entorno de ejecución, etc.) es libre de hacer lo que quiera para obtener el mejor rendimiento, siempre que mantenga el mismo comportamiento. Esto es cierto para la mayoría de los idiomas.
Editar:
Se pueden realizar varias optimizaciones, incluido el intercambio de datos (precisamente porque los datos son inmutables), utilizando la mutabilidad detrás de escena, optimizando las llamadas finales (ya que FP usa mucha recursividad), y otras.
No tienes que recrear todo el árbol. Muchas de las ramas permanecerán iguales y pueden ''reutilizarse''. 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 recibir nuevas ramas.
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 próxima versión del conjunto; en su lugar, solo está creando un nuevo conjunto de bordes. . Puedes hacer esto porque los nodos nunca cambiarán, ni los objetos se mantendrán dentro de ellos.
El beneficio real se encuentra en aplicaciones de un solo hilo, sino en aplicaciones de subprocesos múltiples. Las estructuras de datos inmutables eliminan la necesidad de mecanismos de bloqueo. Si nunca van a cambiar, no tiene que preocuparse por el estado.
Ver
programación funcional: eficiencia de la estructura de datos inmutables
(especialmente mi respuesta que apunta a la charla de Rich Hickey) para la evidencia convincente "general" de que sí, las estructuras inmutables también pueden ser muy eficientes.
En cuanto a qué tan bien 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 es O (logN) (que en términos prácticos es O(1)) ).
no estoy seguro de cómo se implementa esto en el lenguaje, pero las estructuras de datos podrían ser percibidas como inmutables para el programador, pero optimizadas detrás de escena.
por ejemplo, tengo una lista a = [1,2,3,4,5]. Añado 6. b = [a [6]] y ambos pueden ser inmutables. No pierde ningún rendimiento al hacer esto, y es más rápido que copiar los valores.
Entonces, déjame preguntarte, porque no sé, ¿por qué sería más lento hacer las cosas como inmutables? En el caso del árbol, como que veo tu punto. Tendría que volver a crear nodos sobre el nodo actual, supongo, pero no debajo (suponiendo que tengamos punteros de niños y no de padres).