Implementación de estructura de datos inmutable (persistente) tipo matriz con indexación rápida, anexar, anteponer, iteración

Estoy buscando una estructura de datos persistente similar a la matriz (pero inmutable), que permita operaciones rápidas de indexación, anexión, anteposición e iteración (buena localidad).

Clojure proporciona Vector persistente, pero es solo para un apéndice rápido. Scala's Vector tiene efectivamente anexos y antepuestos de tiempo constante, pero no puedo entender cómo se implementa, ya que se basa en la misma estructura de datos (vector de mapa de bits) que el vector Clojure y, según tengo entendido, vector de mapa de bits no puede tener un antecedente rápido sin algunos trucos.

No estoy interesado en la implementación lista para usar, sino en una descripción de cómo implementar esa estructura de datos yo mismo.

El candidato obvio es un árbol binario equilibrado persistente . Todas las operaciones que enumeró se pueden realizar en u O ( lg n ) , utilizando la copia de ruta . Para obtener más detalles sobre cómo lograr este tiempo de ejecución, consulte el libro de Chris Okasaki al que se hace referencia a continuación o mi respuesta aquí .$O(1)$$O(\lg n)$

Por supuesto, como una variante, cada hoja de dicho árbol podría contener una matriz inmutable (una secuencia de valores consecutivos). Esto hace que la actualización de un valor sea menos eficiente, pero podría funcionar bien para su situación, si nunca tiene la intención de modificar un valor existente, solo agregue y anteponga. De esta manera, su vector se representa como una secuencia de secuencias inmutables, representada como un árbol binario equilibrado con matrices inmutables en las hojas. Esto permite una indexación rápida (logarítmica en el número de hojas), un apéndice y un antecedente rápidos, y una iteración rápida. La complejidad asintótica en el peor de los casos no es mejor, pero el rendimiento en la práctica podría ser significativamente mejor.

La referencia estándar es el libro de 1998 de Chris Okasaki "Estructuras de datos puramente funcionales".
Ver también

• ¿Qué clases de estructuras de datos pueden hacerse persistentes?
• ¿Qué hay de nuevo en estructuras de datos puramente funcionales desde Okasaki?
• ¿Cuáles son las preguntas pendientes en estructuras de datos puramente funcionales?
• Diez años de estructuras de datos puramente funcionales

Describí una implementación de dicha estructura de datos en mi artículo sobre coincidencia incremental de expresiones regulares: consulte http://jkff.info/articles/ire/#ropes-strings-with-fast-concatenation y el texto debajo y arriba de esa sección .

Es una variedad de un árbol de altura constante (como B-trees o 2-3 árboles). Básicamente es un árbol (2,3), cuyas hojas son matrices (N, 2N-1), para evitar la sobrecarga por elemento. (Una matriz (N, 2N-1) es una matriz cuyas longitudes están en el rango N..2N-1.) Una N más grande proporciona una sobrecarga menor pero aumenta linealmente la complejidad de la división y la concatenación. Operaciones como la indexación, división y concatenación son muy similares a la forma en que funcionan en 2-3 árboles, generalizándose a (N, 2N-1) a nivel de la hoja.