sbcl работает вечно при втором вызове функции

Question

Функция:

При наличии списка lst возвращает все перестановки содержимого списка точно длины k, которая по умолчанию равна длине списка, если не предоставлена.

(defun permute (lst &optional (k (length lst)))
  (if (= k 1)
   (mapcar #'list lst)
   (loop for item in lst nconcing
     (mapcar (lambda (x) (cons item x)) 
             (permute (remove-if (lambda (x) (eq x item)) lst) 
                      (1- k))))))

Проблема: Я использую SLIME в emacs, подключенном к sbcl, я еще не слишком много настраивал. Функция отлично работает на меньших входах, таких как lst = '(1 2 3 4 5 6 7 8) k = 3, что и будет использоваться на практике. Однако, когда я вызываю его с большим вводом дважды подряд, второй вызов никогда не возвращается, а sbcl даже не отображается сверху. Вот результаты на REPL:

CL-USER> (time (nth (1- 1000000) (permute '(0 1 2 3 4 5 6 7 8 9))))
Evaluation took:
12.263 seconds of real time
12.166150 seconds of total run time (10.705372 user, 1.460778 system)
[ Run times consist of 9.331 seconds GC time, and 2.836 seconds non-GC time. ]
99.21% CPU
27,105,349,193 processor cycles
930,080,016 bytes consed

(2 7 8 3 9 1 5 4 6 0)
CL-USER> (time (nth (1- 1000000) (permute '(0 1 2 3 4 5 6 7 8 9))))

И он никогда не возвращается после второго звонка. Я могу только догадываться, что по какой-то причине я делаю что-то ужасное с сборщиком мусора, но не вижу, что именно. У кого-нибудь есть идеи?

Answer 1

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

EQ не для сравнения чисел. Эквалайзер двух чисел может быть истинным или ложным.

Используйте EQL, если вы хотите сравнивать по тождествам, числам по значению или символам. Не эквалайзер.

На самом деле

(remove-if (lambda (x) (eql x item)) list)

это просто

(remove item list)

Для вашего кода ошибка эквалайзера COULD означает, что перестановка вызывается в рекурсивном вызове без фактического удаления номера из списка.

Кроме этого, я думаю, что SBCL просто занят управлением памятью. SBCL на моем Mac приобрела много памяти (больше ГБ) и была занята чем-то. Через некоторое время результат был вычислен.

Ваша рекурсивная функция генерирует огромное количество мусора. LispWorks говорит: 1360950192 байт

Может быть, вы можете придумать более эффективную реализацию?

Обновление: мусор

Lisp обеспечивает некоторое автоматическое управление памятью, но это не освобождает программиста от мысли о космических эффектах.

Lisp использует как стек, так и кучу для выделения памяти. Куча может быть структурирована определенным образом для GC - например, в поколениях, полупространствах и / или областях. Существуют точные сборщики мусора и «консервативные» сборщики мусора (используются SBCL на машинах Intel).

При запуске программы мы видим различные эффекты:

1. обычные рекурсивные процедуры выделяют место в стеке. Проблема: размер стека обычно фиксирован (хотя некоторые Лиспы могут увеличить его в обработчике ошибок).

2. программа может выделять огромный объем памяти и возвращать большой результат. PERMUTE - это такая функция. Может возвращать очень большие списки.

3. программа может выделять память и использовать ее временно, а затем сборщик мусора может перерабатывать ее. Скорость создания и уничтожения может быть очень высокой, даже если программа не использует большой объем фиксированной памяти.

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

1. Заменить рекурсию итерацией. Заменить рекурсию хвостовой рекурсией.

2. Возвращать только ту часть результата, которая необходима, и не генерировать полное решение. Если вам нужна n-я перестановка, вычислите ее, а не все перестановки. Используйте ленивые структуры данных, которые вычисляются по требованию. Используйте что-то вроде SERIES, что позволяет использовать потоковые, но эффективные вычисления. См. SICP, PAIP и другие продвинутые книги по Лиспу.

3. Повторное использование памяти с менеджером ресурсов. Повторно используйте буферы вместо того, чтобы распределять объекты постоянно. Используйте эффективный сборщик мусора со специальной поддержкой для сбора эфемерных (недолговечных) объектов. Иногда это также может помочь деструктивно модифицировать объекты вместо выделения новых объектов.

Выше рассматриваются космические проблемы реальных программ. В идеале наши компиляторы или инфраструктура времени выполнения могут предоставлять некоторую автоматическую поддержку для решения этих проблем. Но на самом деле это не очень работает. Большинство систем Lisp предоставляют низкоуровневую функциональность для решения этой проблемы, а Lisp предоставляет изменяемые объекты - потому что опыт реальных программ на Lisp показал, что программисты хотят использовать их для оптимизации своих программ. Если у вас есть большое CAD-приложение, которое вычисляет форму турбинных лопаток, то теоретические / пуристические представления о неизменяемой памяти просто не применимы - разработчику нужен более быстрый / меньший код и меньший объем времени выполнения.

Answer 2

SBCL на большинстве платформ использует сборщик мусора поколений, что означает, что выделенная память, которая сохраняется больше, чем некоторое количество собраний, будет реже рассматриваться для сбора. Ваш алгоритм для данного тестового примера генерирует столько мусора, что он вызывает GC столько раз, что фактические результаты, которые, очевидно, должны пережить всю среду выполнения функции, сохраняются, то есть перемещаются в конечное поколение, которое собирается либо очень редко или нет вообще. Поэтому при стандартных настройках для 32-разрядных систем второй запуск будет исчерпан (к примеру, 512 МБ можно увеличить с помощью параметров времени выполнения).

Зафиксированные данные можно собирать мусором, вручную вызывая сборщик с помощью (sb-ext:gc :full t). Это, очевидно, зависит от реализации.

Answer 3

Судя по выводу, вы смотрите на slime-repl, верно?

Попробуйте перейти в буфер "* inferior-lisp *", вы, вероятно, увидите, что SBCL опустился до ldb (встроенный отладчик низкого уровня). Скорее всего, вам удалось взорвать стек вызовов.