sbcl работает навсегда на втором вызове функции
Функция:
Учитывая список 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))))))
Проблема: я использую СЛИЗЬ в 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))))
И это никогда не возвращается из второго вызова. Я могу только предположить, что по некоторым причинам делаю что-то ужасное к сборщику "мусора", но я не вижу что. У кого-либо есть какие-либо идеи?
3 ответа
Одна ошибка в вашем коде - это то, что вы используете эквалайзер. EQ сравнивает на идентичность.
Эквалайзер не предназначен для сравнения чисел. Эквалайзер двух чисел может быть истинным или ложным.
Используйте EQL, если вы хотите сравнивать по идентичности, числам по значению или символам. Не эквалайзер.
На самом деле
(remove-if (lambda (x) (eql x item)) list)
- это просто
(remove item list)
Для вашего кода ошибка EQ МОЖЕТ означать, что перестановка вызывается в рекурсивном вызове без фактического удаления номера из списка.
Помимо этого, я думаю, что SBCL просто занят управлением памятью. SBCL на моем Mac приобрел много памяти (более ГБ) и был чем-то занят. Через некоторое время результат был вычислен.
Ваша рекурсивная функция генерирует огромное количество «мусора». LispWorks говорит: 1360950192 байта
Может быть, вы можете придумать более эффективную реализацию?
Обновление: мусор
Lisp обеспечивает некоторое автоматическое управление памятью, но это не освобождает программиста от размышлений о пространственных эффектах .
Lisp использует как стек, так и кучу для выделения памяти. Куча может быть определенным образом структурирована для GC - например, по поколениям, полупространствам и / или областям. Существуют точные сборщики мусора и «консервативные» сборщики мусора (используемые SBCL на машинах Intel).
Когда программа запускается, мы можем видеть различные эффекты:
обычные рекурсивные процедуры выделяют место в стеке. Проблема: размер стека обычно фиксирован (хотя некоторые Лиспы могут увеличивать его в обработчике ошибок).
программа может выделить огромный объем памяти и вернуть большой результат. PERMUTE - такая функция. Он может возвращать очень большие списки.
программа может выделять память и временно использовать ее, а затем сборщик мусора может ее переработать. Скорость создания и уничтожения может быть очень высокой, даже если программа не использует большой объем фиксированной памяти.
Но есть еще проблемы. Но для каждого из вышеперечисленных программист на Лисп (и любой другой программист, использующий реализацию языка со сборкой мусора) должен научиться с этим справляться.
Заменить рекурсию итерацией. Замените рекурсию хвостовой рекурсией.
Возвращать только ту часть результата, которая необходима, и не генерировать полное решение. Если вам нужна n-я перестановка, вычислите ее, а не все перестановки. Используйте ленивые структуры данных, которые вычисляются по запросу. Используйте что-то вроде SERIES, что позволяет использовать потоковое, но эффективное вычисление. См. SICP, PAIP и другие книги по продвинутому Lisp.
Повторное использование памяти с помощью диспетчера ресурсов. Повторно используйте буферы вместо постоянного выделения объектов. Используйте эффективный сборщик мусора со специальной поддержкой для сбора эфемерных (недолговечных) объектов. Иногда также может помочь деструктивное изменение объектов вместо выделения новых объектов.
Выше касается пространственных задач реальных программ.В идеале наши компиляторы или среда выполнения могут предоставлять некоторую автоматическую поддержку для решения этих проблем. Но на самом деле это не работает. Большинство систем Lisp предоставляют низкоуровневую функциональность для решения этой проблемы, а Lisp предоставляет изменяемые объекты - потому что опыт реальных программ на Лиспе показал, что программисты действительно хотят использовать их для оптимизации своих программ. Если у вас есть большое приложение САПР, которое вычисляет форму лопаток турбины, то теоретические / пуристические представления о неизменяемой памяти просто не применимы - разработчику нужен более быстрый / меньший код и меньшее время выполнения.
SBCL на большинстве платформ использует генерационный сборщик мусора, что означает, что выделенная память, которая переживет более некоторого количества сборов, будет реже рассматриваться для сбора. Ваш алгоритм для данного тестового случая генерирует так много мусора, что запускает GC столько раз, что фактические результаты, которые, очевидно, должны пережить все время выполнения функции, становятся tenured, то есть перемещаются в последнее поколение, которое собирается либо очень редко, либо не собирается вообще. Поэтому при стандартных настройках для 32-битных систем при втором запуске закончится куча (512 МБ, может быть увеличена с помощью опций времени выполнения).
Задержанные данные могут быть собраны в мусор, если вручную запустить сборщик командой (sb-ext:gc :full t). Это, очевидно, зависит от реализации.
Судя по выводу, вы смотрите на slime-repl, верно?
Попробуйте перейти на буфер "*inferior-lisp*", вероятно, вы увидите, что SBCL опустился до ldb (встроенный низкоуровневый отладчик). Вероятнее всего, вам удалось разрушить стек вызовов.