Pregunta impar relacionada con el proyecto euler 72 (lisp)

votos
5

Reconozco que hay un patrón obvio en la salida de esto, solo quiero saber por qué el REPL de lispbox se cancela cuando intento ejecutar cualquier cosa> 52. Además, cualquier sugerencia para mejorar el código es más que bienvenida. ^ - ^

(defun count-reduced-fractions (n d sum)
  (setf g (gcd n d))
  (if (equal 1 d)
      (return-from count-reduced-fractions sum)
      (if (zerop n)
          (if (= 1 g)
              (count-reduced-fractions (1- d) (1- d) (1+ sum))
              (count-reduced-fractions (1- d) (1- d) sum))
          (if (= 1 g)
              (count-reduced-fractions (1- n) d (1+ sum))
              (count-reduced-fractions (1- n) d sum)))))

Todo lo que obtengo cuando llamo

(count-reduced-fractions 53 53 0)

es

Evaluación abortada

No tiene mucho sentido para mí, teniendo en cuenta que se ejecutará (y devolverá el resultado preciso) en todos los números debajo de eso, y que podría (si quisiera) hacer 53 en mi cabeza, en papel o en una línea a la vez en lisp. Incluso probé en muchos números diferentes, mayores de 53, para asegurarme de que no era específico de 53. Nada funciona.

Publicado el 10/12/2008 a las 01:03
fuente por usuario
En otros idiomas...                            


4 respuestas

votos
6

Este comportamiento insinúa una falta de optimización de llamada de cola, por lo que su recursión sopla la pila. Una posible razón es que ha declarado la optimización de depuración.

Por cierto, no es necesario que hagas una llamada explícita a return-from. Dado que sumes un símbolo de autoevaluación, puede cambiar esta línea

(return-from count-reduced-fractions sum)

a

sum

edit: Explicación del cambio propuesto: "suma" se evalúa a su propio valor, que se convierte en el valor de retorno de la instrucción "if", que (ya que esta es la última instrucción en el defun) se convierte en el valor de retorno de la función.

editar: Explicación de la optimización declamada: puede agregar lo siguiente a su nivel superior:

(declaim (optimize (speed 3)
                   (debug 0)))

o use lo mismo, pero con en declarelugar de declaimcomo la primera declaración en su función. También podría probar (espacio 3) y (seguridad 0) si no funciona.

La optimización de llamada de cola significa que una llamada de función cuyo valor devuelto se devuelve directamente se traduce en un reemplazo de cuadro en la pila (en lugar de acumularse), "aplanando" de forma efectiva una llamada de función recursiva a un bucle y eliminando las llamadas de función recursiva. Esto hace que la depuración sea un poco más difícil, ya que no hay llamadas de función donde las espere, resp. usted no sabe qué tan "profundo" en una recursión se produce un error (como si hubiera escrito un bucle para comenzar). Su entorno puede realizar algunas declamaciones predeterminadas que debe anular para habilitar el TCO.

editar: simplemente volviendo a esta pregunta, ¿qué es g? Creo que de verdad quieres

(let ((g (gcd n d)))
  ;; ...
  )
Respondida el 10/12/2008 a las 01:21
fuente por usuario

votos
3

Supongo que hay un límite de profundidad de pila incorporado con lispbox. Como Common Lisp no garantiza que las funciones recursivas de cola usen un espacio de pila constante, es posible que cada invocación de fracciones de conteo reducido agregue otra capa en la pila.

Por cierto, SBCL ejecuta este algoritmo sin problemas.

* (count-reduced-fractions 53 53 0)
881

* (count-reduced-fractions 100 100 0)
3043
Respondida el 10/12/2008 a las 01:11
fuente por usuario

votos
1

Como una cuestión de estilo, puede hacer d y suma opcional.

(defun test (n &optional (d n) (sum 0)) .. )
Respondida el 10/12/2008 a las 01:15
fuente por usuario

votos
0

Probablemente un desbordamiento de pila (heh).

Respondida el 10/12/2008 a las 01:10
fuente por usuario

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more