Вопрос в стиле Lisp: запоминание (предупреждение: содержит решение для проекта euler # 14) - PullRequest
Новая
       19

Вопрос в стиле Lisp: запоминание (предупреждение: содержит решение для проекта euler # 14)

3 голосов
/ 18 августа 2010

Я просто пытаюсь выучить какой-нибудь Лисп, так что у меня проблемы с проектом Эйлера. Я нашел проблему нет. 14 интересного (поэтому, если вы планируете решить эту проблему, прекратите читать сейчас, потому что я поместил свое решение внизу). С моим алгоритмом он был очень медленным, но после использования запоминания (я скопировал функцию из книги Пола Грэхема «на Лиспе») он стал намного быстрее (около 4-8 секунд).

Мой вопрос об этой куче предупреждений, которые я получил: Я делаю что-то неправильно? Могу ли я улучшить свой стиль? 

> ;; 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

Это код: 

 (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)))

Большое спасибо и простите за возможные ошибки, я только начинаю с Lisp. Br

UPDATE: Я хочу поделиться окончательным кодом, который я написал. использование настраиваемой внешней хеш-таблицы для запоминания и улучшения финального цикла. 

(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))))

1 Ответ

1 голос
/ 19 августа 2010

Это плохой стиль для setq неизвестного имени.Предполагается, что вы хотите создать новую глобальную специальную переменную, а затем задать ее, но это следует сделать явным, сначала введя эти привязки.Вы делаете это на верхнем уровне, используя вместо этого defvar (или defparameter или defconstant), а в лексических блоках - let, do, multiple-value-bind или аналогичные конструкции.

...