Modificación de masa eficiente de estructuras de datos persistentes

Question

Entiendo cómo se usan típicamente los árboles para modificar las estructuras de datos persistentes (crear un nuevo nodo y reemplazar todos sus antecesores).

Pero, ¿y si tengo un árbol de 10.000 nodos y tengo que modificar 1000 de ellos? No quiero ir y crear miles de nuevas raíces, solo necesito la raíz nueva que resulta de modificar todo a la vez.

Por ejemplo: Tomemos un árbol binario persistente, por ejemplo. En el caso del nodo de actualización única, realiza una búsqueda hasta que encuentra el nodo, crea uno nuevo con las modificaciones y los elementos secundarios anteriores, y crea antepasados ​​nuevos hasta la raíz.

En el caso de la actualización masiva podríamos hacer: En lugar de simplemente actualizar un solo nodo, va a actualizar 1000 nodos en una sola pasada.

En el nodo raíz, la lista actual es la lista completa. Luego divide esa lista entre los que coinciden con el nodo izquierdo y los que coinciden con el derecho. Si ninguno coincide con uno de los niños, no descienda a él. A continuación, desciende al nodo izquierdo (suponiendo que haya coincidencias), divide su lista de búsqueda entre sus elementos secundarios y continúa. Cuando tiene un solo nodo y una coincidencia, lo actualiza y vuelve a subir, reemplazando y actualizando ancestros y otras ramas, según corresponda.

Esto daría como resultado una sola raíz nueva aunque modificó cualquier cantidad de nodos.

Answer 1

Este tipo de operaciones de "modificación masiva" a veces se llama actualizaciones masivas. Por supuesto, los detalles variarán dependiendo exactamente de qué tipo de estructura de datos esté trabajando y qué tipo de modificaciones está tratando de realizar.

Los tipos típicos de operaciones pueden incluir "eliminar todos los valores que satisfagan alguna condición" o "incrementar los valores asociados con todas las teclas de esta lista". Con frecuencia, estas operaciones se pueden realizar en una sola caminata sobre toda la estructura, tomando el tiempo de O (n).

Parece preocupado por la asignación de memoria involucrada en la creación de "1000 de nuevas raíces". La asignación típica para realizar las operaciones una a la vez sería O (k log n), donde k es la cantidad de nodos que se modifican. La asignación típica para realizar la caminata única en toda la estructura sería O (n). Lo que es mejor depende de k y n.

En algunos casos, puede disminuir la cantidad de asignación, a cambio de un código más complicado, prestando especial atención a los cambios que se produzcan. Por ejemplo, si tiene un algoritmo recursivo que devuelve un árbol, puede modificar el algoritmo para devolver un árbol junto con un booleano que indica si algo ha cambiado. El algoritmo podría verificar esos booleanos antes de asignar un nuevo nodo para ver si el nodo antiguo puede ser reutilizado de manera segura. Sin embargo, las personas no suelen molestarse con este control adicional a menos y hasta que tengan evidencia de que la asignación de memoria adicional es realmente un problema.

Answer 2

Puede encontrar una implementación particular de lo que está buscando en Clojure's (y ClojureScript's) transients.

En resumen, dada una estructura de datos persistente e inmutable, una versión transitoria de la misma realizará cambios usando una mutación destructiva (eficiente en la asignación), que puede volver a una estructura de datos persistente cuando esté hecho con sus operaciones sensibles al rendimiento.Solo es en la transición a una estructura de datos persistente que se crean nuevas raíces (por ejemplo), amortizando así el costo asociado sobre el número de operaciones lógicas que realizó en la estructura mientras estaba en su forma transitoria.