Вернувшись на простые множители числа


Я пытаюсь создать функцию prime-factors что возвращает простые множители числа. Чтобы сделать это, я создал is-prime функции и prime-factors-helper что будет делать рекурсивную проверку главных факторов.

(defun is-prime (n &optional (d (- n 1))) 
  (if (/= n 1) (or (= d 1)
          (and (/= (rem n d) 0)
               (is-prime  n (- d 1)))) ()))

(defun prime-factors-helper (x n)
   (if (is-prime x) 
       (list x) 
       (if (is-prime n) 
            (if (AND (= (mod x n) 0) (<= n (/ x 2)))
                (cons n (prime-factors-helper (/ x n) n))
                (prime-factors-helper x (+ 1 n)))       
            (prime-factors-helper x (+ 1 n)))))

(defun prime-factors (x)
    (prime-factors-helper x 2)) 

У меня есть проблема оптимизации. Когда у меня есть большое количество таких, как 123456789Я получаю это сообщение об ошибке "переполнение стека (стек размер 261120)". Я считаю, что правильный ответ (prime-factors 123456789) это (3 3 3607 3803)моя программа будет занимать так много времени, чтобы найти следующим премьер-фактор, как только он создает список с двух первых элементов (3 3). Как я могу оптимизировать мой код?

 CL-USER 53 > (prime-factors 512)
 (2 2 2 2 2 2 2 2 2)

 CL-USER 54 > (prime-factors 123456789)

 Stack overflow (stack size 261120).
   1 (abort) Return to level 0.
   2 Return to top loop level 0.

 Type :b for backtrace or :c <option number> to proceed.
 Type :bug-form "<subject>" for a bug report template or :? for other options


198
6
задан 19 марта 2018 в 12:03 Источник Поделиться
Комментарии
2 ответа

Есть несколько проблем с вашим кодом.

Стиль


  1. is-prime Это C/Java в стиле. Lispers использовать primep или prime-number-p.

  2. zerop яснее, чем (= 0 ...).

  3. Lispers использовать отступы, а не парень подсчета, чтобы прочитать код. Ваш
    таким образом, код практически нечитаем. Пожалуйста, используйте в Emacs, если вы не
    знаете, как отформатировать правильно сюсюкать.

Переполнение стека

is-prime это хвостовой рекурсии, так что если вы скомпилировать его, он должен стать
простой цикл, и здесь не должно быть никаких проблем стек.

Впрочем, не спешите с этим.

Алгоритм

Количество итераций

Давайте использовать trace чтобы увидеть
проблемы:

> (prime-factors 17)
1. Trace: (IS-PRIME '17)
2. Trace: (IS-PRIME '17 '15)
3. Trace: (IS-PRIME '17 '14)
4. Trace: (IS-PRIME '17 '13)
5. Trace: (IS-PRIME '17 '12)
6. Trace: (IS-PRIME '17 '11)
7. Trace: (IS-PRIME '17 '10)
8. Trace: (IS-PRIME '17 '9)
9. Trace: (IS-PRIME '17 '8)
10. Trace: (IS-PRIME '17 '7)
11. Trace: (IS-PRIME '17 '6)
12. Trace: (IS-PRIME '17 '5)
13. Trace: (IS-PRIME '17 '4)
14. Trace: (IS-PRIME '17 '3)
15. Trace: (IS-PRIME '17 '2)
16. Trace: (IS-PRIME '17 '1)
16. Trace: IS-PRIME ==> T
15. Trace: IS-PRIME ==> T
14. Trace: IS-PRIME ==> T
13. Trace: IS-PRIME ==> T
12. Trace: IS-PRIME ==> T
11. Trace: IS-PRIME ==> T
10. Trace: IS-PRIME ==> T
9. Trace: IS-PRIME ==> T
8. Trace: IS-PRIME ==> T
7. Trace: IS-PRIME ==> T
6. Trace: IS-PRIME ==> T
5. Trace: IS-PRIME ==> T
4. Trace: IS-PRIME ==> T
3. Trace: IS-PRIME ==> T
2. Trace: IS-PRIME ==> T
1. Trace: IS-PRIME ==> T
(17)

Вы делаете 17 повторений, когда только (isqrt 17) = 4 итераций не требуется.

Пересчеты

Теперь скомпилируйте is-prime чтобы включить рекурсию в цикл и посмотреть:

> (prime-factors 12345)
1. Trace: (IS-PRIME '12345)
1. Trace: IS-PRIME ==> NIL
1. Trace: (IS-PRIME '2)
1. Trace: IS-PRIME ==> T
1. Trace: (IS-PRIME '12345)
1. Trace: IS-PRIME ==> NIL
1. Trace: (IS-PRIME '3)
1. Trace: IS-PRIME ==> T
1. Trace: (IS-PRIME '4115)
1. Trace: IS-PRIME ==> NIL
1. Trace: (IS-PRIME '3)
1. Trace: IS-PRIME ==> T
1. Trace: (IS-PRIME '4115)
1. Trace: IS-PRIME ==> NIL
1. Trace: (IS-PRIME '4)
1. Trace: IS-PRIME ==> NIL
1. Trace: (IS-PRIME '4115)
1. Trace: IS-PRIME ==> NIL
1. Trace: (IS-PRIME '5)
1. Trace: IS-PRIME ==> T
1. Trace: (IS-PRIME '823)
1. Trace: IS-PRIME ==> T
(3 5 823)

Вы проверяете делением одного числа несколько раз!

Дополнительная оптимизация

primep можно найти делитель, а не просто проверить делением.

Оптимизированный алгоритм

(defun compositep (n &optional (d (isqrt n)))
"If n is composite, return a divisor.
Assumes n is not divisible by anything over d."
(and (> n 1)
(> d 1)
(if (zerop (rem n d))
d
(compositep n (- d 1)))))

(defun prime-decomposition (n)
"Return the prime decomposition of n."
(let ((f (compositep n)))
(if f
(nconc (prime-decomposition (/ n f))
(prime-decomposition f))
(list n))))

Отметим, что одним окончательной оптимизации можно -
мемоизацияиз
compositep:

(let ((known-composites (make-hash-table)))
(defun compositep (n &optional (d (isqrt n)))
"If n is composite, return a divisor.
Assumes n is not divisible by anything over d."
(multiple-value-bind (value found-p) (gethash n known-composites)
(if found-p
value
(setf (gethash n known-composites)
(and (> n 1)
(> d 1)
(if (zerop (rem n d))
d
(compositep n (- d 1)))))))))

или, еще лучше, из prime-decomposition:

(let ((known-decompositions (make-hash-table)))
(defun prime-decomposition (n)
"Return the prime decomposition of n."
(or (gethash n known-decompositions)
(setf (gethash n known-decompositions)
(let ((f (compositep n)))
(if f
(append (prime-decomposition (/ n f))
(prime-decomposition f))
(list n)))))))

обратите внимание на использование или append вместо
nconc
.

Еще один интересный оптимизации меняется итерации в
compositep С нисходящего на восходящий.
Это должно значительно ускорить его, как он прекратит рано еще
часто:

(let ((known-composites (make-hash-table)))
(defun compositep (n)
"If n is composite, return a divisor.
Assumes n is not divisible by anything over d."
(multiple-value-bind (value found-p) (gethash n known-composites)
(if found-p
value
(setf (gethash n known-composites)
(loop for d from 2 to (isqrt n)
when (zerop (rem n d))
return d))))))

ПС. Это идентично https://stackoverflow.com/a/49369108/850781

4
ответ дан 19 марта 2018 в 01:03 Источник Поделиться

Ваш is-prime очень неоптимальным в нескольких аспектах.

И. нет смысла проверять на простые множители число выше неотъемлемую часть этого числа квадратный корень.

Второй. Кроме 2, все остальные простые множители числа-Нечетные (если таковые имеются), так что вы только нужно проверить по самый корень(н)/2 чисел.

Раздел III. И ваша рекурсия не выглядит хвост-оптимизируется, так что вам нужно либо изменить его, так что вы получите один хвост-вызов (если ваш СХ реализация осознает хвост оптимизация), или превратить его в итеративном построении (которое, я считаю, весьма доступен в CL, гораздо больше, чем на схеме).

Ведь вам не нужно получить список все простые делители числа, чтобы сказать, что это составная; и даже меньше, вы должны держать стека на каждое число меньше, чем он.

prime-factors-helper менее чувствителен (все рекурсивные вызовы либо в хвост или хвост по модулю минусы-один), но все равно вам не нужно проверять каждую цифру меньше, чем Х (помню, только до sqrt(X) и только половина из них).

Кроме того, в отношении (= expr 0)не сл стандартной библиотеке имеется примитивный предикат для сравнения с нулем, как zero? в схему?

2
ответ дан 19 марта 2018 в 01:03 Источник Поделиться