Обычные настройки Lisp SBCL Loop

Question

Я использую метод Project 5 Euler методом грубой силы для проверки производительности CL-кода.Я новичок в языке и хочу знать, как делать такие вещи.Я написал реализацию C, которая работает примерно за 1,3 секунды.Моя первоначальная наивная реализация CL выполняется примерно за 15 секунд.

Вот мой начальный код CL

(defpackage :problem-5
  (:use #:cl)
  (:export :divides-even-p
           :has-all-divisors
           :smallest-multiple)
  )

(in-package :problem-5)

(defun divides-even-p (num divisor)
  (= 0 (rem num divisor))
  )

(defun has-all-divisors (num start stop)
  (loop for divisor from start to stop do
       (cond
         ((not (divides-even-p num divisor)) (return-from has-all-divisors nil))
         )
       (+ divisor 1)
       )
  t
  )

(defun smallest-multiple (n)
  (do ((multiple 1 (+ multiple 1)))
      ((has-all-divisors multiple 1 n) (format t "~A" multiple))
    ))

(time (smallest-multiple 20))

Уловки, о которых я читал до сих пор: 1) оптимизация для скорости и безопасности, 2) встроенные функции и 3) явно заданные типы переменных.Применяя эти вещи, я получаю следующий код

(defpackage :problem-5
  (:use #:cl)
  (:export :divides-even-p
           :has-all-divisors
           :smallest-multiple)
  )

(in-package :problem-5)

(declaim (optimize (speed 3) (safety 0))
         (inline divides-even-p)
         (inline has-all-divisors)
         )

(defun divides-even-p (num divisor)
  (declare (type integer num divisor))

  (zerop (rem num divisor))
  )

(defun has-all-divisors (num start stop)
  (declare (type integer num start stop))

  (loop for divisor of-type integer from start to stop do
       (cond
         ((not (divides-even-p num divisor)) (return-from has-all-divisors nil))
         )
       )
  t
  )

(defun smallest-multiple ()
  (do ((multiple 1 (+ multiple 1)))
      ((has-all-divisors multiple 2 20) (format t "~A" multiple))
    ))

(time (smallest-multiple))

Теперь, когда я запускаю эту версию, она запускается за 7 секунд вместо 15. Ускорение в 2 раза, поэтому в правильном направлении.Что еще можно сделать, чтобы ускорить его?Самая яркая вещь для меня - это цикл do в наименьшем кратном.Во-первых, я не мог понять, как указать тип для множественной переменной.Как ты это делаешь?Есть ли лучший способ сделать циклы с открытым концом, которые производят меньше кода?Как вы будете пытаться увеличить производительность отсюда?Код C запускается примерно за 1,3 секунды, поэтому я был бы рад получить его до 2 или 3 секунд.

Answer 1

Для одного вы можете использовать fixnum вместо integer. Последний включает в себя все целые числа, первые только те, которые вписываются в машинное слово минус несколько битов тега (обычно что-то около 61 или 62 бит).

Объявление в цикле do приходит в начале тела:

(do ((m 1 (1+ m)))
    ((has-all-divisors m 2 20)
     m)
  (declare (fixnum m)))

Вы также можете использовать loop здесь:

(loop :for m :of-type fixnum :upfrom 1
      :when (has-all-divisors m 2 20)
        :do (return m))

Улучшения кода:

• Пожалуйста, не оставляйте круглые скобки, как обрезки ногтей.

• Используйте if для условного выражения с двумя ветвями.

• Loop имеет ключевое слово always:

  (loop :for divisor :of-type fixnum :from start :to stop
        :always (divides-even-p num divisor))
  

Answer 2

Я не полный эксперт по CL, но хотел бы дать несколько советов, которые могут оказаться полезными.

Общий стиль

Не следует оставлять закрытиескобка на дополнительной строке.Смотрите, например, здесь для некоторых замечаний по стилю.Кроме того, строка документации поможет другим и вам в будущем понять ваш код.

Производительность

Я не рассматривал свое собственное решение этой проблемы, но яПредположим, что указание fixnum вместо integer приведет к увеличению производительности в 2 раза и должно быть возможным для этой проблемы.

Цикл

Вы можете написать has-all-divisors идиоматичнее, используя loop s always предложение:

(defun has-all-divisors (num start stop)
  (declare (type fixnum num start stop))
  (loop for divisor of-type fixnum from start to stop
        always (divides-even-p num divisor)))

Альтернативное решение

Если я правильно помню эту проблему, вы можете использовать другой алгоритм, которыйдолжно быть намного быстрее.Соберите все простые множители целых чисел от 2 до 20 и постройте их произведение.