¿Qué tan rápido es Data.Array?

El documentation de Data.Array lee:¿Qué tan rápido es Data.Array?

Haskell proporciona matrices de corte giratorias, que pueden ser considerados como funciones cuyos dominios son isomorfos a subconjuntos contiguos de los números enteros. Las funciones restringidas de esta manera se pueden implementar de manera eficiente; en particular, un programador puede razonablemente esperar un acceso rápido a los componentes.

me pregunto ¿cómo puede rápida y (!)(//) ser. ¿Puedo esperar una complejidad O (1) de estos, como lo hubiera hecho con sus contrapartes imperativas?

Fuente

2011-09-02 R. Martinho Fernandes

En general, sí, debe poder esperar O (1) desde ! aunque no estoy seguro de si eso está garantizado por la norma.

Es posible que desee ver el paquete de vectores si desea matrices más rápidas (mediante el uso de la fusión de secuencias). También está mejor diseñado.

Tenga en cuenta que // es probablemente O (n) porque tiene que atravesar la lista (como lo haría un programa imperativo). Si necesita mucha mutación, puede usar MArray o MVector.

Fuente

2011-09-02 21:21:13 alternative

'(//)' es realmente linar en el _size de la matriz_, ya que tiene que hacer una nueva copia de la matriz. Sin embargo, usando matrices mutables, espero que sea lineal en el número de actualizaciones. – hammar

@hammar es lineal en ambos, ya que debe copiar el conjunto así como iterar sobre la lista. // es bastante inútil, sin embargo, en un MArray porque no necesita la funcionalidad de actualización masiva. – alternative

Sí, por supuesto. Sin embargo, eso solo importa si está actualizando algunos elementos más de una vez. – hammar

Respuesta

Cuestiones relacionadas