data structures - Implementar un deque inmutable como un árbol binario equilibrado?

data-structures functional-programming

Question

He estado pensando durante un tiempo acerca de cómo implementar una deque (es decir, una cola de doble extremo) como una estructura de datos inmutables.

Parece que hay diferentes formas de hacer esto. AFAIK, las estructuras de datos inmutables generalmente son jerárquicas , por lo que partes importantes de esta pueden reutilizarse después de modificar operaciones como la inserción o eliminación de un elemento.

Eric Lippert tiene two articles en su blog sobre este tema, junto con implementaciones de muestra en C #.

Ambas implementaciones me parecen más elaboradas de lo que realmente es necesario. ¿No podrían los deques simplemente implementarse como árboles binarios, donde los elementos solo pueden insertarse o eliminarse en la "izquierda" (la parte frontal ) y en la "derecha" (la parte posterior ) del árbol?

 o
/ /
… …
/ /
… …
/ / / /
front --> L … … R <-- back

Además, el árbol se mantendría razonablemente equilibrado con las rotaciones:

• rotaciones correctas al insertarlas en la parte delantera o al retirarlas de la parte posterior, y
• rotaciones a la izquierda al retirarlas del frente o insertarlas en la parte posterior.

Eric Lippert es, en mi opinión, una persona muy inteligente a quien respeto profundamente, pero aparentemente él no consideró este enfoque. Por lo tanto, me pregunto, ¿fue por una buena razón? ¿Mi forma sugerida de implementar Deques es ingenua?

Answer 1

¿No podrían los deques simplemente implementarse como árboles binarios, donde los elementos solo pueden insertarse o eliminarse en la "izquierda" (la parte frontal) y en la "derecha" (la parte posterior) del árbol?

Absolutamente. Una versión modificada de un árbol de altura equilibrada, árboles AVL en particular, sería muy fácil de implementar. Sin embargo, significa que el relleno de la cola basada en árboles con n elementos requiere tiempo O(n lg n) ; debe disparar para una deque que tenga características de rendimiento similares a la contraparte mutable.

Puede crear un deque inmutable directo con operaciones amortizadas de tiempo constante para todas las operaciones principales usando dos pilas, una pila izquierda y otra derecha. PushLeft y PushRight corresponden a valores de empuje en la pila izquierda y derecha, respectivamente. Puede obtener Deque.Hd y Deque.Tl desde LeftStack.Hd y LeftStack.Tl; si su LeftStack está vacío, configure LeftStack = RightStack.Reverse y RightStack = stack vacío.

type ''a deque = Node of ''a list * ''a list // ''
let peekFront = function
| Node([], []) -> failwith "Empty queue"
| Node(x::xs, ys) -> x
| Node([], ys) -> ys |> List.rev |> List.head
let peekRear = function
| Node([], []) -> failwith "Empty queue"
| Node(xs, y::ys) -> y
| Node(xs, []) -> xs |> List.rev |> List.head
let pushFront v = function
| Node(xs, ys) -> Node(v::xs, ys)
let pushRear v = function
| Node(xs, ys) -> Node(xs, v::ys)
let tl = function
| Node([], []) -> failwith "Empty queue"
| Node([], ys) -> Node(ys |> List.rev |> List.tail, [])
| Node(x::xs, ys) -> Node(xs, ys)

Esta es una implementación muy común, y es muy fácil de optimizar para un mejor rendimiento.

Answer 2

Como señaló Daniel, implementar deques inmutables con árboles de búsqueda equilibrada bien conocidos como AVL o árboles rojo-negro da Θ (lg n) la peor de las complicaciones del caso. Algunas de las implementaciones que Lippert analiza pueden parecer elaboradas a primera vista, pero hay muchos deques inmutables con o (lg n) peor o complejidad promedio o amortizada que se construyen a partir de árboles equilibrados junto con dos ideas simples:

1. Invierta las espinas

   Para realizar operaciones de deque en un árbol de búsqueda equilibrado tradicional, necesitamos acceso a los extremos, pero solo tenemos acceso al centro. Para llegar al extremo izquierdo, debemos navegar por los indicadores secundarios izquierdos hasta que finalmente lleguemos a un callejón sin salida. Sería preferible tener un puntero a los extremos izquierdo y derecho sin todo ese esfuerzo de navegación. De hecho, realmente no necesitamos acceder al nodo raíz muy a menudo. Guardemos un árbol de búsqueda equilibrado para que el acceso a los extremos sea O (1).

   Aquí hay un ejemplo en C de cómo normalmente podría almacenar un árbol AVL:

   struct AVLTree {
   const char * value;
   int height;
   struct AVLTree * leftChild;
   struct AVLTree * rightChild;
   };

   Para configurar el árbol de modo que podamos comenzar en los bordes y avanzar hacia la raíz, cambiamos el árbol y almacenamos todos los punteros a lo largo de las rutas desde la raíz hasta los niños de la izquierda y de la derecha en sentido inverso . (Estos caminos se llaman espina dorsal izquierda y derecha , respectivamente). Al igual que al revertir una lista enlazada individualmente, el último elemento se convierte en el primero, por lo que ahora se puede acceder fácilmente al elemento secundario situado más a la izquierda.

   Esto es un poco difícil de entender. Para ayudar a explicarlo, imagine que solo hizo esto para la columna izquierda:

   struct LeftSpine {
   const char * value;
   int height;
   struct AVLTree * rightChild;
   struct LeftSpine * parent;
   };

   En cierto sentido, el niño de la izquierda es ahora la "raíz" del árbol. Si dibujaste el árbol de esta manera, se vería muy extraño, pero si simplemente tomas el dibujo normal de un árbol y reviertes todas las flechas en el lomo izquierdo, el significado de la estructura LeftSpine debería ser más claro. El acceso al lado izquierdo del árbol ahora es inmediato. Lo mismo se puede hacer por la columna derecha:

   struct RightSpine {
   double value;
   int height;
   struct AVLTree * leftChild;
   struct RightSpine * parent;
   };

   Si almacena tanto el lomo izquierdo como el derecho, así como el elemento central, tiene acceso inmediato a ambos extremos. La inserción y eliminación aún pueden ser Ω (lg n), ya que las operaciones de reequilibrio pueden requerir atravesar todo el lomo izquierdo o derecho, pero simplemente ver los elementos más a la izquierda y a la derecha es ahora O (1).

   Un ejemplo de esta estrategia se usa para hacer ataques puramente funcionales con implementaciones en SML y Java ( más documentación ). Esta es también una idea clave en muchos otros productos inmutables con rendimiento o (lg n).

2. Limitó el trabajo de equilibrio

   Como se indicó anteriormente, insertar en el extremo izquierdo o derecho de un árbol AVL puede requerir Ω (lg n) tiempo para atravesar la columna vertebral. Aquí hay un ejemplo de un árbol AVL que demuestra esto:

   Un árbol binario completo se define por inducción como:

   • Un árbol binario completo de altura 0 es un nodo vacío.
   • Un árbol binario completo de altura n + 1 tiene un nodo raíz con árboles binarios completos de altura n como hijos.

   Al presionar un elemento a la izquierda de un árbol binario completo, necesariamente aumentará la altura máxima del árbol. Dado que los árboles AVL anteriores almacenan esa información en cada nodo, y dado que cada árbol a lo largo de la columna izquierda de un árbol binario completo es también un árbol binario completo, empuja un elemento a la izquierda de una deque AVL que resulta ser un árbol binario completo requerirá incrementar los valores de altura de Ω (lg n) a lo largo del lomo izquierdo.

   (Dos notas al respecto: (a) Puede almacenar árboles AVL sin mantener la altura en el nodo, sino que solo conserva la información del balance (más a la izquierda, más a la derecha, más alta o incluso más). Esto no cambia el rendimiento del ejemplo anterior. (b) En los árboles AVL, puede que necesite no solo actualizar Ω (lg n) actualizaciones de información de equilibrio o altura, sino Ω (lg n) operaciones de reequilibrio. No recuerdo los detalles de esto, y puede estar solo en eliminaciones, en lugar de inserciones).

   Para lograr o (lg n) deque operaciones, tenemos que limitar este trabajo. Deques inmutables representados por árboles equilibrados usualmente usan al menos una de las siguientes estrategias:

   • Anticipa dónde se necesitará un reequilibrio . Si está usando un árbol que requiere un reequilibrio o (lg n) pero sabe dónde se necesitará ese reequilibrio y puede llegar lo suficientemente rápido, puede realizar sus operaciones de deque en o (lg n) tiempo. Deques que usan esto como una estrategia almacenará no solo dos punteros en el deque (los extremos de las espinas izquierda y derecha, como se discutió anteriormente), sino un pequeño número de punteros de salto a lugares más altos a lo largo de las espinas. Las operaciones Deque pueden acceder a las raíces de los árboles apuntados por los punteros de salto en el tiempo O (1). Si se mantienen los punteros de salto o (lg n) para todos los lugares donde será necesario reequilibrar (o cambiar la información del nodo), las operaciones de deque pueden tomar un tiempo o (lg n).

     (Por supuesto, esto hace que el árbol sea realmente un dag, ya que los árboles en las espinas apuntadas por punteros de salto también son apuntadas por sus hijos en la columna vertebral. Las estructuras de datos inmutables generalmente no se llevan bien con gráficos no arbóreos, reemplazar un nodo señalado por más de otro nodo requiere reemplazar todos los otros nodos que lo señalan. He visto esto solucionado simplemente eliminando los punteros que no son de salto, convirtiendo el dag en un árbol. Lista de enlaces individuales con punteros de salto como una lista de listas. Cada lista subordinada contiene todos los nodos entre el encabezado de esa lista y su puntero de salto. Esto requiere cierto cuidado para tratar con punteros de salto parcialmente superpuestos, y una explicación completa es probablemente no es apropiado para esto aparte).

     Este es uno de los trucos utilizados por Tsakalidis en su artículo "Árboles AVL para búsqueda localizada" para permitir O (1) operaciones de deque en árboles AVL con una condición de equilibrio relajado. También es la idea principal utilizada por Kaplan y Tarjan en su artículo "Deques en tiempo real puramente funcional con catenación" y un refinamiento posterior de eso por Mihaesau y Tarjan . Las "listas de salto deterministas" de Munro et al. También merecen una mención aquí, aunque la traducción de listas de omisiones a una configuración inmutable mediante el uso de árboles a veces cambia las propiedades que permiten dicha modificación eficiente cerca de los extremos. Para ejemplos de la traducción, vea "Omitir árboles, una estructura de datos alternativa a Omitir listas en un enfoque concurrente" de Messeguer, " Explorando la dualidad entre listas de omisiones y árboles de búsqueda binarios " de Dean y Jones , y "Sobre la equivalencia de Lamoureux y Nickerson" B-trees y listas de omisiones deterministas " .

   • Haz el trabajo a granel . En el ejemplo de árbol binario completo anterior, no se necesita un reequilibrio en un impulso, pero los nodos Ω (lg n) deben actualizar su información de altura o saldo. En lugar de realmente hacer el incremento, simplemente podría marcar el lomo en los extremos como si necesitara un incremento.

     Una forma de entender este proceso es por analogía con los números binarios. (2 ^ n) -1 está representado en binario por una cadena de n 1. Al agregar 1 a este número, debe cambiar todos los 1 a 0 y luego agregar 1 al final. El siguiente Haskell codifica números binarios como cadenas de bits no vacías, menos significativas primero.

     data Bit = Zero | One
     type Binary = (Bit,[Bit])
     incr :: Binary -> Binary
     incr (Zero,x) = (One,x)
     incr (One,[]) = (Zero,[One])
     incr (One,(x:xs)) =
     let (y,ys) = incr (x,xs)
     in (Zero,y:ys)

     incr es una función recursiva, y para los números de la forma (One,replicate k One) , incr se llama a sí mismo Ω (k) veces.

     En cambio, podríamos representar grupos de bits iguales solo por el número de bits en el grupo. Los bits o grupos de bits vecinos se combinan en un grupo si son iguales (en valor, no en número). Podemos incrementar en O (1) tiempo:

     data Bits = Zeros Int | Ones Int
     type SegmentedBinary = (Bits,[Bits])
     segIncr :: SegmentedBinary -> SegmentedBinary
     segIncr (Zeros 1,[]) = (Ones 1,[])
     segIncr (Zeros 1,(Ones n:rest)) = (Ones (n+1),rest)
     segIncr (Zeros n,rest) = (Ones 1,Zeros (n-1):rest)
     segIncr (Ones n,[]) = (Zeros n,[Ones 1])
     segIncr (Ones n,(Zeros 1:Ones m:rest)) = (Zeros n,Ones (m+1):rest)
     segIncr (Ones n,(Zeros p:rest)) = (Zeros n,Ones 1:Zeros (p-1):rest)

     Como segIncr no es recursivo y no llama a ninguna función que no sean más y menos en Ints, puede ver que toma O (1) vez.

     Algunos de los deques mencionados en la sección anterior titulada "Anticipar dónde se necesitará el reequilibrio" utilizan en realidad una técnica diferente inspirada numéricamente llamada "sistemas numéricos redundantes" para limitar el trabajo de reequilibrio a O (1) y localizarlo rápidamente. Las representaciones numéricas redundantes son fascinantes, pero posiblemente demasiado lejos para esta discusión. Elmasry et al. "Sistema de números y estructuras de datos estrictamente regulares" no es un mal lugar para comenzar a leer sobre ese tema. Las "matrices flexibles de un solo lado Bootstrapping" de Hinze también pueden ser útiles.

     En "Hacer estructuras de datos persistentes" , Driscoll et al. describen la reposición lenta , que atribuyen a Tsakalidis. Lo aplican a árboles rojo-negros, que pueden ser reequilibrados después de la inserción o eliminación con O (1) rotaciones (pero Ω (lg n) recolocaciones) (ver Tarjan "Actualizando un árbol equilibrado en O (1) rotaciones" ). El núcleo de la idea es marcar una gran ruta de nodos que deben recolocarse pero no girarse. Una idea similar se utiliza en los árboles AVL en las versiones anteriores de Brown & Tarjan "Un algoritmo de fusión rápida" . (Las versiones más recientes del mismo trabajo usan 2-3 árboles; no he leído los más nuevos y no sé si usan alguna técnica, como el reordenamiento lento).

   • Aleatorizar Los Treaps, mencionados anteriormente, pueden implementarse en una configuración funcional para que realicen operaciones de deyección en tiempo O (1) en promedio. Debido a que los deques no necesitan inspeccionar sus elementos, este promedio no es susceptible a un rendimiento de degradación de entrada malicioso, a diferencia de los árboles de búsqueda binarios simples (sin reequilibrio), que son rápidos en la entrada promedio. Treaps utiliza una fuente independiente de bits aleatorios en lugar de confiar en la aleatoriedad de los datos.

     En una configuración persistente, las trampas pueden ser susceptibles de un rendimiento degradado a partir de entradas maliciosas con un adversario que puede (a) usar versiones anteriores de una estructura de datos y (b) medir el rendimiento de las operaciones. Debido a que no tienen ninguna garantía de saldo en el peor de los casos, las trampas pueden llegar a ser bastante desequilibradas, aunque esto debería ocurrir rara vez. Si un adversario espera una operación de deque que lleva mucho tiempo, puede iniciar esa misma operación repetidamente para medir y aprovechar un árbol posiblemente desequilibrado.

     Si esto no es una preocupación, las trampas son una estructura de datos atractiva y simple. Están muy cerca del árbol vertebral AVL descrito anteriormente.

     Las listas de omisiones, mencionadas anteriormente, también podrían ser susceptibles de implementaciones funcionales con O (1) operaciones de deque de tiempo promedio.

     Las primeras dos técnicas para delimitar el trabajo de reequilibrio requieren modificaciones complejas a las estructuras de datos, mientras que generalmente ofrecen un análisis simple de la complejidad de las operaciones de deque. La aleatorización, junto con la siguiente técnica, tienen estructuras de datos más simples pero un análisis más complejo. El análisis original de Seidel y Aragón no es trivial , y hay algunos análisis complejos de probabilidades exactas utilizando matemáticas más avanzadas que las que aparecen en los documentos citados anteriormente - ver "Patrones en árboles de búsqueda binaria aleatoria" de Flajolet et al .

   • Amortizar Hay varios árboles balanceados que, cuando se ven desde las raíces hacia arriba (como se explica en "Reverse the Spines", arriba), ofrecen O (1) tiempo amortizado de inserción y eliminación. Las operaciones individuales pueden tomar Ω (lg n) tiempo, pero ponen al árbol en un estado tan agradable que una gran cantidad de operaciones después de la costosa operación serán baratas.

     Lamentablemente, este tipo de análisis no funciona cuando las versiones antiguas del árbol aún existen. Un usuario puede realizar operaciones en el árbol viejo, casi fuera de balance, muchas veces sin operaciones intermedias baratas.

     Una forma de obtener límites amortizados en un entorno persistente fue inventado por Chris Okasaki . No es simple explicar cómo la amortización sobrevive a la capacidad de utilizar versiones antiguas arbitrarias de una estructura de datos, pero si mal no recuerdo, el primer documento de Okasaki (que yo sepa) sobre el tema tiene una explicación bastante clara. Para obtener explicaciones más completas, consulte su tesis o su libro .

     Según lo entiendo, hay dos ingredientes esenciales. En primer lugar, en lugar de simplemente garantizar que ocurra un cierto número de operaciones baratas antes de cada operación costosa (el enfoque habitual de la amortización), en realidad designa y configura esa operación costosa específica antes de realizar las operaciones baratas que pagarán por ella. En algunos casos, la operación está programada para comenzar (y finalizar) solo después de muchos pasos intermedios. En otros casos, la operación en realidad solo tiene programados O (1) pasos en el futuro, pero las operaciones económicas pueden hacer parte de la costosa operación y luego reprogramarla más para más adelante. Si un adversario busca repetir una operación costosa una y otra vez, en realidad está reutilizando la misma operación programada cada vez. Este intercambio es donde entra el segundo ingrediente.

     El cálculo se establece usando la pereza . Un valor diferido no se calcula inmediatamente, pero, una vez realizado, su resultado se guarda. La primera vez que un cliente necesita inspeccionar un valor diferido, se calcula su valor. Los clientes posteriores pueden usar ese valor en caché directamente, sin tener que recalcularlo.

     #include <stdlib.h>
     struct lazy {
     int (*oper)(const char *);
     char * arg;
     int* ans;
     };
     typedef struct lazy * lazyop;
     lazyop suspend(int (*oper)(const char *), char * arg) {
     lazyop ans = (lazyop)malloc(sizeof(struct lazy));
     ans->oper = oper;
     ans->arg = arg;
     return ans;
     }
     void force(lazyop susp) {
     if (0 == susp) return;
     if (0 != susp->ans) return;
     susp->ans = (int*)malloc(sizeof(int));
     *susp->ans = susp->oper(susp->arg);
     }
     int get(lazyop susp) {
     force(susp);
     return *susp->ans;
     }

     Los constructos de pereza están incluidos en algunos ML, y Haskell es flojo por defecto. Bajo el capó, la pereza es una mutación, lo que lleva a algunos autores a llamarlo un "efecto secundario". Eso podría considerarse malo si ese tipo de efecto secundario no funciona bien con los motivos para seleccionar una estructura de datos inmutables en primer lugar, pero, por otro lado, pensar en la pereza como un efecto secundario permite la aplicación de técnicas tradicionales de análisis amortizado para estructuras de datos persistentes, tal como se menciona en un documento de Kaplan, Okasaki y Tarjan titulado "Listas encapsulables confluentemente persistentes simples" .

     Considere nuevamente al adversario de arriba que intenta forzar repetidamente el cálculo de una operación costosa. Después de la primera fuerza del valor perezoso, toda fuerza restante es barata.

     En su libro, Okasaki explica cómo construir deques con O (1) tiempo amortizado requerido para cada operación. Es esencialmente un árbol B +, que es un árbol donde todos los elementos se almacenan en las hojas, los nodos pueden variar en la cantidad de hijos que tienen, y cada hoja tiene la misma profundidad. Okasaki utiliza el método de inversión de la columna vertebral que se discutió anteriormente, y suspende (es decir, almacena como un valor diferido) las espinas sobre los elementos de la hoja.

     Una estructura de Hinze y Paterson llamada "Árboles de dedo: una estructura de datos de propósito general simple" está a medio camino entre los deques diseñados por Okasaki y las "Representaciones puramente funcionales de listas ordenadas cativables" de Kaplan y Tarjan . La estructura de Hinze y Paterson se ha vuelto muy popular.

     Como evidencia de lo difícil que es comprender el análisis amortizado, los árboles de dedo de Hinze y Paterson se implemented frequently without holgazanería, haciendo que los límites de tiempo no sean O (1) pero todavía O (lg n). Una implementación que parece usar la pereza es la de dotnet funcional . Ese proyecto también incluye una implementación de valores perezosos en C # que podría ayudar a explicarlos si faltara mi explicación anterior.

¿Podrían los deques implementarse como árboles binarios? Sí, y la complejidad de su peor caso cuando se usa persistentemente no sería peor que las presentadas por Eric Lippert. Sin embargo, los árboles de Eric en realidad no son lo suficientemente complicados para obtener O (1) operaciones de deque en un entorno persistente, aunque solo por un pequeño margen de complejidad (haciendo que el centro sea flojo) si está dispuesto a aceptar un rendimiento amortizado. Una vista diferente pero también simple de las trampas puede obtener O (1) el rendimiento esperado en un entorno funcional, suponiendo un adversario que no es demasiado complicado. Obtener O (1) operaciones de deque en el peor de los casos con una estructura similar a un árbol en una configuración funcional requiere una complejidad un poco más compleja que las implementaciones de Eric.

Dos notas finales (aunque este es un tema muy interesante y me reservo el derecho de agregar más más tarde) :-)

1. Casi todos los deques mencionados anteriormente también son árboles de búsqueda de dedo. En un entorno funcional, esto significa que pueden dividirse en el elemento i-ésimo en O (lg (min (i, ni))) tiempo y dos árboles de tamaño nym pueden concatenarse en O (lg (min (n, m) )) hora.

2. Conozco dos formas de implementar deques que no usan árboles. Okasaki presenta uno en su libro y tesis y el documento al que he vinculado anteriormente. El otro usa una técnica llamada "reconstrucción global" y se presenta en "Deques en tiempo real, máquinas de Turing multitarjeta y programación puramente funcional" de Chuang y Goldberg .

Answer 3

Las otras respuestas son increíbles. Les agregaré que elegí la implementación de árbol de dedo de un deque porque hace un uso inusual e interesante del sistema de tipo genérico. La mayoría de las estructuras de datos son recursivas en su estructura , pero esta técnica coloca la recursión también en el sistema de tipos que no había visto antes; Pensé que podría ser de interés general.

Answer 4

Si usa un árbol binario equilibrado, las inserciones y eliminaciones en ambos extremos son O (lg N) (tanto el promedio como el peor caso). El enfoque utilizado en las implementaciones de Eric Lippert es más eficiente, ejecutándose en tiempo constante en el caso promedio (el peor caso aún es O (lg N)).

Recuerde que modificar un árbol inmutable implica reescribir a todos los padres del nodo que está modificando. Entonces, para una deque, no quieres que el árbol esté equilibrado; en su lugar, desea que los nodos L y R estén lo más cerca posible de la raíz, mientras que los nodos en el medio del árbol pueden estar más alejados.