sbcl corre siempre en segunda llamada de la función

Question

La función:

Dada una lista de retorno LST todas las permutaciones de los contenidos de la lista exacta de longitud k, que por defecto es la longitud de la lista si no previstos.

(defun permute (lst &optional (k (length lst))) 
    (if (= k 1) 
    (mapcar #'list lst) 
    (loop for item in lst nconcing 
    (mapcar (lambda (x) (cons item x)) 
      (permute (remove-if (lambda (x) (eq x item)) lst) 
         (1- k)))))) 

El problema: estoy usando BABA en emacs conectados a SBCL, no he hecho demasiado personalización aún. La función funciona bien en entradas más pequeñas como lst = '(1 2 3 4 5 6 7 8) k = 3, que es lo que más se utilizará en la práctica. Sin embargo, cuando lo llamo con una entrada grande dos veces seguidas, la segunda llamada nunca regresa y sbcl ni siquiera aparece en la parte superior. Estos son los resultados en el REPL:

CL-USER> (time (nth (1- 1000000) (permute '(0 1 2 3 4 5 6 7 8 9)))) 
Evaluation took: 
12.263 seconds of real time 
12.166150 seconds of total run time (10.705372 user, 1.460778 system) 
[ Run times consist of 9.331 seconds GC time, and 2.836 seconds non-GC time. ] 
99.21% CPU 
27,105,349,193 processor cycles 
930,080,016 bytes consed 

(2 7 8 3 9 1 5 4 6 0) 
CL-USER> (time (nth (1- 1000000) (permute '(0 1 2 3 4 5 6 7 8 9)))) 

Y nunca vuelve de la segunda llamada. Solo puedo adivinar que por alguna razón estoy haciendo algo horrible para el recolector de basura, pero no puedo ver qué. ¿Alguien tiene alguna idea?

Answer 1

Una cosa que está mal en su código es su uso de EQ. EQ se compara con la identidad.

EQ no es para comparar números. EQ de dos números puede ser verdadero o falso.

Use EQL si desea comparar por identidad, números por valor o caracteres. No EQ.

En realidad

(remove-if (lambda (x) (eql x item)) list) 

es sólo

(remove item list) 

Para el código de error de la ecualización PODRÍAN significar que permute es llamado en la llamada recursiva sin llegar a un número eliminado de la lista.

Aparte de eso, creo que SBCL solo está ocupado con la gestión de memoria. SBCL en mi Mac adquirió mucha memoria (más de un GB) y estaba ocupado haciendo algo. Después de un tiempo el resultado fue calculado.

Su función recursiva genera una enorme cantidad de "basura". LispWorks dice: 1360950192 bytes

¿Tal vez se te ocurra una implementación más eficiente?

Actualización: basura

Lisp proporciona una cierta gestión de memoria automática, pero eso no libera al programador de pensar acerca de los efectos espaciales.

Lisp usa tanto una pila como el montón para asignar memoria. El montón puede estar estructurado de cierta manera para el CG, por ejemplo en generaciones, medios espacios y/o áreas. Hay recolectores de basura precisos y recolectores de basura "conservadores" (utilizados por SBCL en las máquinas Intel).

Cuando se ejecuta un programa podemos ver varios efectos:

1. procedimientos recursivos normales asignar espacio en la pila. Problema: el tamaño de la pila suele ser fijo (aunque algunos Lisps pueden aumentarlo en un controlador de errores).

2. un programa puede asignar gran cantidad de memoria y devolver un resultado grande. PERMUTE es una función así. Puede devolver listas muy grandes.

3. un programa puede asignar memoria y usarla temporalmente y luego el recolector de basura puede reciclarla. La tasa de creación y destrucción puede ser muy alta, a pesar de que el programa no utiliza una gran cantidad de memoria fija.

Sin embargo, hay más problemas. Pero para cada uno de los anteriores, el programador de Lisp (y cualquier otro programador que use una implementación de lenguaje con recolección de basura) tiene que aprender cómo lidiar con eso.

1. Reemplazar la recursión con iteración. Reemplace la recursividad con recursividad de cola.

2. Devuelve solo la parte del resultado que se necesita y no genera la solución completa. Si necesita la n-ésima permutación, calcule eso y no todas las permutaciones. Utiliza estructuras de datos perezosas que se computan según demanda. Utilice algo como SERIES, que permite usar un cómputo similar a un flujo, pero eficiente. Ver SICP, PAIP y otros libros avanzados de Lisp.

3. Reutiliza la memoria con un administrador de recursos. Reutilice búferes en lugar de asignar objetos todo el tiempo. Use un recolector de basura eficiente con soporte especial para recolectar objetos efímeros (efímeros). A veces también puede ayudar a modificar objetos de manera destructiva, en lugar de asignar nuevos objetos.

Above se ocupa de los problemas de espacio de los programas reales. Idealmente, nuestros compiladores o infraestructura de tiempo de ejecución pueden proporcionar algún soporte automático para tratar estos problemas. Pero en realidad esto no funciona realmente. La mayoría de los sistemas Lisp proporcionan una funcionalidad de bajo nivel para lidiar con esto y Lisp proporciona objetos mutables, porque la experiencia de los programas Lisp del mundo real ha demostrado que los programadores sí los quieren usar para optimizar sus programas. Si tiene una aplicación de CAD grande que computa la forma de las palas de la turbina, entonces las vistas teóricas/purísticas sobre la memoria no mutable simplemente no se aplican: el desarrollador desea el código más rápido/más pequeño y la huella de tiempo de ejecución más pequeña.

Answer 2

Desde el aspecto de la salida, estás viendo Slime-repl, ¿verdad?

Intente cambiar al búfer "* inferior-lisp *", probablemente verá que SBCL ha bajado al ldb (depurador de bajo nivel incorporado). Lo más probable es que haya logrado volar la pila de llamadas.

Answer 3

SBCL en la mayoría de las plataformas utiliza el recolector de basura generacional, lo que significa que la memoria asignada que sobrevive a más de un número de colecciones se considerará más raramente para la recolección. Su algoritmo para el caso de prueba dado genera tanta basura que desencadena GC tantas veces que los resultados reales, que obviamente tienen que sobrevivir todo el tiempo de ejecución de la función, se guardan, es decir, se mueven a una generación final que se recopila muy raramente o no en absoluto. Por lo tanto, la segunda ejecución, en configuraciones estándar para sistemas de 32 bits, se quedará sin montón (512 MB, se puede aumentar con las opciones de tiempo de ejecución).

Los datos permanentes se pueden recolectar como basura activando manualmente el recolector con (sb-ext:gc :full t). Obviamente, esto depende de la implementación.