Estructuras de datos en lisp

Question

Tengo un problema simple: reunir objetos en una lista y recorrer esta lista al revés. Parece bastante fácil, pero este código es parte del cálculo de alta carga. Es bastante natural usar conses porque toma O (1) al agregar un nuevo elemento y en el acceso secuencial. Pero, ¿qué debo hacer si necesito una lista efectiva de doble enlace para atravesarla fácilmente en ambas direcciones? Use (reversa)? Toma O (n) la memoria y el tiempo, por lo que tomará O (n^2) en mi caso (que es realmente malo). ¿Usar (último) o (agregar)? La misma historia: O (n). Realmente no entiendo dónde encontrar (excepto el código fuente) información sobre la complejidad computacional de las funciones estándar de la biblioteca. ¿Depende de la implementación? ¿Y qué debo hacer para la implementación de varias estructuras de datos estándar? ¿Hay alguna guía sobre el uso de conses de manera efectiva?

Answer 1

Si usa Common Lisp, puede usar vectores en su lugar. Los vectores pueden tener un puntero de relleno y/o pueden ser ajustables. Entonces puedes usar el vector-push para agregar elementos a un vector. El puntero de relleno crecerá. Si el vector es ajustable, también será más grande si es necesario. Como los vectores son matrices unidimensionales, puede acceder a los elementos con un índice a su gusto.

Consulte las opciones de MAKE-ARRAY para crear dicho vector.

VECTOR-PUSH y VECTOR-PUSH-EXTEND son las funciones para agregar elementos.

Answer 2

Si hace (reverse) una vez y luego recorre la lista invertida en orden secuencial, el total debe ser solo O (2n) tiempo (O (n) para la configuración, y luego otra O (n) para atravesar) y O (n) memoria.

Una lista doblemente enlazada no es terriblemente complicada. Como usted sabe, se hace una lista de las células de cons donde el automóvil apunta al objeto que el cdr apunta a la siguiente celda de cons en la lista.

Una manera de hacer una lista doblemente enlazada es tener lugar el punto de CDR a otra celda contras cuya CDR puntos a la siguiente celda contras de la lista y cuyo automóvil puntos a la célula desventajas anteriores la lista. Luego usa cddr para avanzar y cdar para retroceder.

No sé que las funciones de la biblioteca estándar tienen cualquier complejidad garantizada. A menos que la especificación especifique, sería definido por la implementación.