Lisp style question: memoization (caution: contains solution for project Euler # 14)

I'm just trying to learn some Lisp, so I run into problems with the project Euler. I found no problem. 14 is interesting (so if you plan to solve this problem, stop reading now because I pasted my solution below). It was so slow with my algorithm, but after using memoization (I copied the function from Paul Graham "in the Lisp book") it was much faster (about 4-8 seconds).

My question is about this heap of warnings I received: Am I doing something wrong? Can I improve my style?

> ;; Loading file
> /euler-lisp/euler-14.lisp
> ... WARNING in COLLATZ-SERIE :
> COLLATZ-SERIE-M is neither declared
> nor bound, it will be treated as if it
> were declared SPECIAL. WARNING in
> COLLATZ-SERIE : COLLATZ-SERIE-M is
> neither declared nor bound, it will be
> treated as if it were declared
> SPECIAL. WARNING in COMPILED-FORM-314
> : COLLATZ-SERIE-M is neither declared
> nor bound, it will be treated as if it
> were declared SPECIAL. (525 837799) 
> Real time: 18.821894 sec. Run time:
> 18.029127 sec. Space: 219883968 Bytes GC: 35, GC time: 4.080254 sec. Las
> siguientes variables especiales no han
> sido definidas:  COLLATZ-SERIE-M 0
> errores, 0 advertencias ;; Loaded file

This is the code:

 (defun collatz (n)
      (if (evenp n) (/ n 2) (+ (* 3 n) 1)))

    (defun memoize (fn)
      (let ((cache (make-hash-table :test #'equal)))
        #'(lambda (&rest args)
            (multiple-value-bind (val win) (gethash args cache)
              (if win
                  val
                (setf (gethash args cache)
                      (apply fn args)))))))

    (defun collatz-serie (n)
      (cond ((= n 1) (list 1))
        ((evenp n) (cons n (funcall collatz-serie-m (/ n 2))))
        (t (cons n (funcall collatz-serie-m (+ (* 3 n) 1))))))

    (defun collatz-serie-len (n)
      (length (collatz-serie n)))

    (setq collatz-serie-m (memoize #'collatz-serie))

    (defun gen-series-pairs (n)
      (loop for i from 1 to n collect 
           (list (collatz-serie-len i) i)))

    (defun euler-14 (&key (n 1000000))
      (car (sort (gen-series-pairs n) #'(lambda (x y) (> (car x) (car y))))))

    (time (print (euler-14)))

Thank you very much and forgive possible errors, I'm just starting with Lisp. Br

UPDATE: , . - memoization .

(defvar *cache* (make-hash-table :test #'equal))

(defun collatz (n)
       (if (evenp n) (/ n 2) (+ (* 3 n) 1)))

(defun collatz-serie (n)
  (cond ((= n 1) (list 1))
    ((evenp n) (cons n (collatz-serie (/ n 2))))
    (t (cons n (collatz-serie (+ (* 3 n) 1))))))

(defun collatz-serie-new (n)
  (labels ((helper (n len) 
             (multiple-value-bind (val stored?) (gethash n *cache*)
               (if stored? 
                   val
                 (setf (gethash n *cache*) (cond ((= n 1) len)
                                                 ((evenp n) (+ len (helper (/ n 2) len)))
                                                 (t (+ len (helper (+ (* 3 n) 1) len)))))))))
    (helper n 1)))

;; learning how to loop
(defun euler-14 (&key (n 1000000))
  (loop with max = 0 and pos = 0 
        for i from n downto 1 
        when (> (collatz-serie-new i) max) 
        do (setf max (collatz-serie-new i)) and do (setf pos i) 
        finally (return (list max pos))))
+3
1

setq . , , , , . , defvar ( defparameter defconstant) , let, do, multiple-value-bind .

+1

Source: https://habr.com/ru/post/1760392/


All Articles