Refinamiento de función lisp

Question

He hecho el Graham Common Lisp Capítulo 5 Ejercicio 5, que requiere una función que toma un objeto X y un vector V, y devuelve una lista de todos los objetos que preceden inmediatamente a X en V.

funciona así:

> (preceders #\a "abracadabra") 
(#\C#\d #r) 

he hecho la versión recursiva:

(defun preceders (obj vec &optional (result nil) &key (startt 0)) 
    (let ((l (length vec))) 
    (cond ((null (position obj vec :start startt :end l)) result) 
      ((= (position obj vec :start startt :end l) 0) 
      (preceders obj vec result 
         :startt (1+ (position obj vec :start startt :end l)))) 
      ((> (position obj vec :start startt :end l) 0) 
      (cons (elt vec (1- (position obj vec :start startt :end l))) 
       (preceders obj vec result 
          :startt (1+ (position obj vec 
               :start startt 
               :end l)))))))) 

funciona correctamente, pero mis maestros me da la siguiente crítica:

"Esto llama longitud repetidamente. No es tan malo con los vectores, pero sigue siendo innecesario. Un código más eficiente y más flexible (para el usuario) es definir esto como otras funciones de procesamiento de secuencia. Utilice: parámetros de palabras clave de inicio y fin, como lo hacen las otras funciones de secuencia, con los mismos valores iniciales predeterminados. la longitud debería llamarse como mucho una vez. "

Estoy consultando el libro de texto de Common Lisp y google, pero parece que hay poca ayuda en este aspecto: no sé a qué se refiere con" using: start y: finalice los parámetros de palabra clave ", y no tengo ni idea de cómo" llamar por única vez ". Les agradecería si pudieran darme una idea de cómo refinar mi código para cumplir con el requisito que mi profesor publicó. Gracias una gran cantidad

ACTUALIZACIÓN:

Hola chicos, ahora han llegado con el siguiente código:

(defun preceders (obj vec 
        &optional (result nil) 
        &key (start 0) (end (length vec)) (test #'eql)) 
    (let ((pos (position obj vec :start start :end end :test test))) 
    (cond ((null pos) result) 
      ((zerop pos) (preceders obj vec result 
           :start (1+ pos) :end end :test test)) 
      (t (preceders obj vec (cons (elt vec (1- pos)) result) 
         :start (1+ pos) :end end :test test))))) 

me sale esa crítica:

"Cuando se tiene una llamada recursiva complejo que se repite de forma idéntica en más de una rama, a menudo es más fácil de hacer la llamada primera, guardarlo en una variable local, y luego usar la variable de una manera mucho más simple si o COND "

Además, para mi versión iterativa de la función:.

(defun preceders (obj vec) 
    (do ((i 0 (1+ i)) 
     (r nil (if (and (eql (aref vec i) obj) 
         (> i 0)) 
        (cons (aref vec (1- i)) r) 
        r))) 
     ((eql i (length vec)) (reverse r)))) 

consigo la crítica

"Comience el DO en un punto mejor y elimine la prueba> 0 repetida"

¿Podría compartir sus ideas conmigo, creo que este es mi paso final hacia el éxito? ¡Muchas gracias!

Answer 1

una lista de parámetros típicos para tal función sería:

(defun preceders (item vector 
        &key (start 0) (end (length vector)) 
         (test #'eql)) 
    ... 
) 

Como se puede ver que tiene los parámetros de inicio y fin.

TEST es la función de comparación predeterminada. Uso (elemento de prueba de llamada (vector i de i)). A menudo también hay un parámetro KEY ...

LENGTH se llama repetidamente para cada llamada recursiva de PRECEDERS.

Haría la versión no recursiva y movería dos índices sobre el vector: uno para el primer elemento y otro para el siguiente.Siempre que el siguiente elemento sea EQL para el artículo que está buscando, inserte el primer elemento en una lista de resultados (si no es miembro).

Para la versión recursiva, escribiría una segunda función a la que llaman los PRECEDORES, que toma dos variables de índice que comienzan con 0 y 1, y usan eso. Yo no llamaría POSICIÓN. Por lo general, esta función es una función local a través de LABELS dentro de PRECEDERS, pero para hacerlo un poco más fácil de escribir, la función auxiliar también puede estar afuera.

(defun preceders (item vector 
        &key (start 0) (end (length vector)) 
         (test #'eql)) 
    (preceders-aux item vector start end test start (1+ start) nil)) 


(defun preceders-aux (item vector start end test pos0 pos1 result) 
    (if (>= pos1 end) 
     result 
     ... 
)) 

¿Eso ayuda?

Aquí está la versión iterativa utilizando BUCLE:

(defun preceders (item vector 
        &key (start 0) (end (length vector)) 
         (test #'eql)) 
    (let ((result nil)) 
    (loop for i from (1+ start) below end 
      when (funcall test item (aref vector i)) 
      do (pushnew (aref vector (1- i)) result)) 
    (nreverse result))) 

Answer 2

Puesto que usted ya tiene una solución que funciona, voy a amplifica una Rainer Joswig's solution, principalmente para hacer comentarios estilísticos relacionados.

(defun preceders (obj seq &key (start 0) (end (length seq)) (test #'eql))   
    (%preceders obj seq nil start end test)) 

La razón principal para tener función auxiliar independiente (que llamo %PRECEDERS, una convención común para indicar que una función es "privado") es eliminar el argumento opcional para el resultado. Usar argumentos opcionales de esa manera en general está bien, pero los argumentos opcionales y los de palabras clave juegan horriblemente juntos, y tener ambos en una sola función es una forma extremadamente eficiente de crear todo tipo de errores difíciles de depurar.

Es una cuestión de gusto hacer que la función de ayudante sea global (usando DEFUN) o local (usando LABELS). Prefiero hacerlo global, ya que significa menos sangría y una depuración interactiva más sencilla. YMMV.

Una posible implementación de la función auxiliar es:

(defun %preceders (obj seq result start end test) 
    (let ((pos (position obj seq :start start :end end :test test))) 
     ;; Use a local binding for POS, to make it clear that you want the 
     ;; same thing every time, and to cache the result of a potentially 
     ;; expensive operation. 
    (cond ((null pos) (delete-duplicates (nreverse result) :test test))    
      ((zerop pos) (%preceders obj seq result (1+ pos) end test)) 
      ;; I like ZEROP better than (= 0 ...). YMMV. 
      (t (%preceders obj seq 
         (cons (elt seq (1- pos)) result) 
         ;; The other little bit of work to make things 
         ;; tail-recursive.  
     (1+ pos) end test))))) 

Además, después de todo eso, creo que debo señalar que también estoy de acuerdo con el consejo de Rainer hacer esto con un bucle explícito en lugar de recursividad, siempre que hacerlo recursivamente no sea parte del ejercicio.

EDIT: Cambié a la convención "%" más común para la función de ayuda. Por lo general, cualquiera sea la convención que utilice, simplemente aumenta el hecho de que solo exporta explícitamente las funciones que conforman su interfaz pública, pero algunas funciones estándar y macros usan un "*" posterior para indicar una funcionalidad variante.

Cambié cosas para eliminar los precedentes duplicados usando la función estándar DELETE-DUPLICATES. Esto tiene el potencial de ser mucho (es decir, exponencialmente) más rápido que los usos repetidos de ADJOIN o PUSHNEW, ya que puede usar una representación de conjunto hash internamente, al menos para funciones de prueba comunes como EQ, EQL y EQUAL.

Answer 3

Responda su primera ACTUALIZACIÓN.

primera pregunta:

ver este

(if (foo) 
    (bar (+ 1 baz)) 
    (bar baz)) 

Eso es lo mismo que:

(bar (if (foo) 
     (+ 1 baz) 
     baz)) 

o:

(let ((newbaz (if (foo) 
       (+ 1 baz) 
       baz))) 
    (bar newbaz)) 

Segundo:

¿Por qué no comenzar con I = 1?

Ver también la versión iterativa en mi otra respuesta ...

Answer 4

La versión iterativo propuesto por Rainer es muy agradable, es compacto y más eficiente, ya que se recorre la secuencia de una sola vez; en contraste con la versión recursiva que llama a position en cada iteración y por lo tanto atraviesa la subsecuencia cada vez. (Editar: Lo siento, yo estaba completamente equivocado en esto última frase, véase el comentario de Rainer)

Si se necesita una versión recursiva, otro enfoque es avanzar en la start hasta que se encuentra con el end, recogiendo el resultado a lo largo de su camino.

(defun precede (obj vec &key (start 0) (end (length vec)) (test #'eql)) 
    (if (or (null vec) (< end 2)) nil 
    (%precede-recur obj vec start end test '()))) 

(defun %precede-recur (obj vec start end test result) 
    (let ((next (1+ start))) 
    (if (= next end) (nreverse result) 
     (let ((newresult (if (funcall test obj (aref vec next)) 
         (adjoin (aref vec start) result) 
         result))) 
     (%precede-recur obj vec next end test newresult))))) 

Por supuesto, esto es sólo otra manera de expresar la versión loop.

prueba:

[49]> (precede #\a "abracadabra") 
(#\r #\C#\d) 
[50]> (precede #\a "this is a long sentence that contains more characters") 
(#\Space #\h #\t #\r) 
[51]> (precede #\s "this is a long sentence that contains more characters") 
(#\i #\Space #\n #\r) 

Además, yo estoy interesado Robert, ha dicho tu maestro por qué no le gusta usar adjoin o pushnew en un algoritmo recursivo?

Answer 5

Una variante ligeramente modofied de la versión de bucle de Rainer:

(defun preceders (item vector 
        &key (start 0) (end (length vector)) 
        (test #'eql)) 
    (delete-duplicates 
    (loop 
     for index from (1+ start) below end 
     for element = (aref vector index) 
     and previous-element = (aref vector (1- index)) then element 
     when (funcall test item element) 
     collect previous-element))) 

Esto hace un mayor uso de las directivas de bucle, y entre otras cosas sólo se accede a cada elemento en el vector de una vez (que mantienen el elemento anterior de la anterior -elemento variable).