Почему это взрывает кучу в Lispworks?

Я пытаюсь решить задачу 14 в Project Euler (найти самую длинную последовательность Коллатца от 1 до 1000000).

Мой код состоит из рекурсивной запоминаемой функции для вычисления длины последовательностей Коллатца, за которой следует цикл для нахождения максимума. Пожалуйста, смотрите код ниже:

(defparameter *collatz* (make-hash-table))
(setf (gethash 1 *collatz*) 0)

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

(loop for i from 1 to 1000000 maximize (n-collatz i))

Это отлично работало в Clozure, но вызывало переполнение кучи в Lispworks. Поскольку он вышел неизящно, я не мог узнать, что произошло. На самом деле, я не понимаю, почему это занимает так много места в куче — самая большая последовательность рекурсии — это 300 с чем-то вызовов. Я пропустил некоторую неэффективность в коде?

Любой вклад приветствуется. Также приветствуются дальнейшие комментарии к коду.

PS: я использую Lispworks Personal Edition, что накладывает ограничение на размер кучи.

ОБНОВЛЕНИЕ Я попытался скомпилировать, как предложил Райнер Джосвиг, но это не помогло.

Что касается комментариев coredump и sds, or действительно лучше, чем if в данном случае, но я не могу заменить хеш-таблицу вектором, потому что последовательность коллатца увеличивается примерно в 50% случаев. После запуска кода в хеш-таблице осталось около 2,5 миллионов записей.

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


lisp common-lisp collatz lispworks
person Paulo Mendes    schedule 08.10.2015    source источник
comment
Я не могу воспроизвести переполнение (здесь нет Lispworks); все, что я могу сказать, это то, что (if X X Y) также пишется как (or X Y)   -  person coredump    schedule 08.10.2015
comment
Вы используете LispWorks Personal Edition? Если это так, то помните, что хеш-таблицы обычно реализуются для массивов с большим количеством неиспользуемых слотов, поэтому ваша хэш-таблица может вырасти настолько, что LispWorks Personal Edition взорвется на пределе кучи, после чего ее сигнатурный запрос выйдет без возможности восстановления.   -  person acelent    schedule 08.10.2015
comment
ОБНОВЛЕНИЕ: я пытался скомпилировать, как предложил Райнер Джосвиг, но это не помогло. Мне интересно, есть ли способ заставить Lispworks компилировать материал более агрессивно.   -  person Paulo Mendes    schedule 09.12.2015

Ответы (5)


arrow_upward
3
arrow_downward

Я вижу здесь две неэффективности:

  1. Вы используете хеш-таблицу, индексированную непрерывной целочисленной последовательностью. Вместо этого вам, вероятно, следует использовать (расширяемый) вектор.

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

По общему признанию, ничто из этого не могло объяснить исчерпание кучи.

person sds    schedule 08.10.2015

arrow_upward
4
arrow_downward

Во-первых, нужно убедиться, что n-collatz скомпилирован:

(compile 'n-collatz)

Или используйте компилятор с помощью обычных команд IDE.

Код, введенный в LispWorks Listener, интерпретируется иначе:

CL-USER 140 > (defun n-collatz (n)
                (if (gethash n *collatz*) (gethash n *collatz*)
                  (setf (gethash n *collatz*)
                        (if (evenp n)
                            (1+ (n-collatz (/ n 2)))
                          (1+ (n-collatz (1+ (* n 3))))))))
N-COLLATZ

CL-USER 141 > #'n-collatz
#<interpreted function N-COLLATZ 40600020CC>

CL-USER 142 > (compile 'n-collatz)
N-COLLATZ
NIL
NIL

CL-USER 143 > #'n-collatz
#<Function N-COLLATZ 4060007054>
person Rainer Joswig    schedule 08.10.2015

arrow_upward
4
arrow_downward

LispWorks просто провалился, увы. Я думаю, что во внутренностях LispWorks есть какая-то утечка или другой сбой управления памятью.

Вы используете личную версию LW, у которой есть ограничение по памяти, и этот материал достигает этого предела. Он поднял диалоговое окно, в котором говорится об этом, а затем уходит.

Коммерческие версии LW работают без проблем.

person Yehouda Harpaz    schedule 28.02.2017

arrow_upward
1
arrow_downward

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

(setf (gethash n collatz))

с номером n больше, чем текущий размер таблицы. Когда вы вызываете make-hash-table без параметра размера, система выбирает значение, зависящее от реализации. Каждый раз, когда это значение превышено, размер таблицы должен изменяться во время выполнения, что потребляет много ресурсов и может привести к упомянутому вами сбою. Чтобы решить эту проблему, вы можете создать таблицу со значением, которое, как вы знаете, не будет превышено:

(defparameter *collatz* (make-hash-table :size 1000000)).
person Leo    schedule 09.10.2015

arrow_upward
1
arrow_downward

Я запускаю 64-разрядную версию LispWorks 7.1.1 на Mac с помощью интерпретатора

CL-USER 1 > (defparameter *collatz* (make-hash-table))
*COLLATZ*

CL-USER 2 > (setf (gethash 1 *collatz*) 0)
0

CL-USER 3 > (defun n-collatz (n)
              (if (gethash n *collatz*)
                  (gethash n *collatz*)
                (setf (gethash n *collatz*)
                      (if (evenp n)
                          (1+ (n-collatz (/ n 2)))
                        (1+ (n-collatz (1+ (* n 3))))))))
N-COLLATZ

CL-USER 4 > (loop for i from 1 to 1000000 maximize (n-collatz i))

Stack overflow (stack size 15998).
  1 (continue) Extend stack by 50%.
  2 (abort) 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.

Итак, выше показано «переполнение стека», а не «переполнение кучи». Обратите внимание, что можно изменить размер стека и продолжить.

Теперь я попробовал это снова в свежем LispWorks, но при компиляции функции:

CL-USER 1 > (defparameter *collatz* (make-hash-table))
*COLLATZ*

CL-USER 2 > (setf (gethash 1 *collatz*) 0)
0

CL-USER 3 > (defun n-collatz (n)
              (if (gethash n *collatz*)
                  (gethash n *collatz*)
                (setf (gethash n *collatz*)
                      (if (evenp n)
                          (1+ (n-collatz (/ n 2)))
                        (1+ (n-collatz (1+ (* n 3))))))))
N-COLLATZ

CL-USER 4 > (compile 'n-collatz)
N-COLLATZ
NIL
NIL

CL-USER 5 > (loop for i from 1 to 1000000 maximize (n-collatz i))
524

Скомпилированный код отлично работает без необходимости наращивания стека.

person Rainer Joswig    schedule 02.05.2019