Pregunta ¿Por qué es Data.Sequence.reverse O (n)?


Los doctores dicen Data.Sequence.reverse Está encendido). ¿No se podría "invertir" un tipo de secuencia finita estableciendo una bandera? (Efectivamente, que terminan para "comenzar a contar" desde.)


5
2018-05-30 15:07


origen


Respuestas:


Si solo tienes una bandera, tendrás problemas. Supongamos que quiero

xs <> reverse xs

¿Cómo podría calcular eso? Con solo una bandera, tendría que realizar un reverso costoso antes de agregar. Para hacer esto derecho, necesitas más banderas, repartidas alrededor del árbol. Todas alrededor del arbol Cada nodo en el árbol necesita llevar información de reversión. Esto definitivamente es posible, pero es un poco caro. Peor aún, cada paso de cada operación tiene que gestionar los indicadores de inversión de forma adecuada, lo que es una pesadilla para cualquiera que tenga que escribir y mantener el código. Esta idea se ha desarrollado en un documento en algún lugar (no recuerdo cuál) pero no es divertido en la práctica.

Si tiene un algoritmo que se basa fundamentalmente en la inversión, entonces debe usar un tipo de secuencia personalizada con muchos indicadores, e incluir solo las operaciones que necesita (si está basando su tipo en Data.Sequence, probablemente deberías robar un bit de cada campo de tamaño). Pero no creo que tales algoritmos sean terriblemente comunes.


3
2018-05-31 06:43



Sí, podría.

Sin embargo, esto agrega un pequeño precio a cada búsqueda (¡primero se debe verificar la bandera!), Y la recompensa solo corresponde a los usuarios que usan reverse mucho. Este último grupo probablemente fue juzgado como pequeño. Ya que lanzar la bandera apropiada sobre el tipo puede hacerse desde el lado del cliente, tiene sentido no pagar este precio en la biblioteca por cada uso de cada función. En cambio, el programador que pretende llamar. reverse Mucho se ve obligado a hacer esta opción de compromiso de rendimiento si lo desean, lo que me parece perfectamente sensato.


4
2018-05-30 17:08



Bien podrias definir

data S a = S { forward :: Seq a , backward :: Seq a }

y luego implementar todas las operaciones con el invariante que

forall a :: Type, s :: S a  : reverse (forward s) == backward s . 

Esto duplica el costo de cada uno, pero da tiempo constante. reverse.


1
2018-05-30 16:30



Creo que se podría hacer en O(1) Si el >< la concatenación admite concatenar xs >< reversed ys sin penalización (se requiere algún corte en la estructura del árbol de dedos).

Buscando Data.Sequence todas las operaciones tienen una contraparte inversa (por ejemplo, takeWhileL ~ takeWhileR) o tomar O(n) (o peor, ej. zip tomar O(min(n1,n2)) luego, invertir seq1 cuando n1<n2 y así) excepto >< operación.

En todo caso, xs >< ys tomará O(min(|xs|,|ys|)) como el peor de los casos (dos de cuatro casos posibles). Esto es en la práctica un poco mejor que O(n) (Se necesita normalizar a una dirección única y revertirla).

Entonces, la pregunta es:

Puede hacerse xs >< reversed ys mejor que O(min(|xs|,|ys|))?

(idealmente O(log(min(|xs|,|ys|))))

Por supuesto, si no usas >< operación, toma la operación inversa O(1) (por ejemplo, usar una bandera para verificar cuándo usar la contraparte izquierda o derecha).

Por otro lado, si el rendimiento de las secuencias invertidas de concatenación es crítico, probablemente exista alguna otra estructura óptima o puede considerar su uso estrategia @ d8d0d65b3f7cf42.


0
2018-05-31 07:52