Как работает классическая сборка мусора в лиспе? Сколько памяти занимает cons-ячейка? - Lisp
Формулировка задачи:
Как работает классическая сборка мусора в лиспе (прочитал в документации, что SBCL использует классическую сборку)? Как работает в данном случае? Как работает в различных реализациях?
Цель задачи была в том, чтобы методом brutforce уместить в портфель размером 360 вещей на максимальную сумму.
Для создания всех вариаций используется функция powerset. Вроде бы её сложность удовлетворяет всем требованиям задачи, однако препод потребовал что бы я добавил в файл с данными еще около пяти вещей, в итоге sbcl начал вылетать с ошибкой нехватки памяти. Но при этом он вылетал и до добавления вещей, если было запустить main два раза -> отсюда вопрос Хранит ли lisp в памяти значение последней вычисленной формы? Если да то понятно откуда нехватка памяти.
Далее, как при mapcar очищается память, каждый раз когда получаем новый элемент удаляем старый єлемент? Или же ожидается какой-то лимит количества мусора?
Мне удалось без проблем строить подсписки из 23 элементов если я даю sbcl 6 гигабайт памяти (всего имею 7.9 в наличии поэтому больше дать не могу), при этом размер такого списка имеет размер в 2^23 списков c цифрами. И при этом задача вполне корректно решается.
Числа в sbcl в 64 битной реализации занимают 8 байт. Сколько занимает каждая cons-ячейка? Сколько занимают структуры? Например моя структура thing?
Файл, со списком вещей и размером рюкзака.
(defun powerset (lst) (loop for i below (expt 2 (length lst)) collect (loop for j below i for x in lst if (logbitp j i) collect x))) (defstruct thing id weight value) (defun read-lines-as-lists (filename) (with-open-file (stream filename) (loop for line = (read-line stream nil) while line collect (read-from-string (concatenate 'string "(" line ")"))))) (defun lists-to-things (lst) (mapcar #'(lambda (x) (make-thing :id (first x) :weight (second x) :value (third x))) lst)) (defun sum-by-param (param things-lst) (reduce #'+ (mapcar param things-lst))) (defun special-print (x) (format t "-----------------------------------~%< weight: ~a, value: ~a >~%" (second x) (third x)) (dolist (i (car x)) (format t "id: ~a,~aweight: ~a,~avalue: ~a~%" (thing-id i) #\tab (thing-weight i) #\tab (thing-value i)))) (defun print-result (x) (special-print (first x)) (when (= (third (first x)) (third (second x))) (print-result (cdr x)))) (defun main (filename) (let ((maxWeight 0) (lst (read-lines-as-lists filename))) (setf maxWeight (car (car lst)) lst ((lambda (x) (sort x #'> :key #'third)) (remove-if #'(lambda (x) (> (second x) maxWeight)) (mapcar #'(lambda (x) (list x (sum-by-param 'thing-weight x) (sum-by-param 'thing-value x))) (powerset (lists-to-things (cdr lst))))))) (print-result lst)))
360 1 10 60 2 20 200 3 55 120 4 30 120 5 40 110 6 40 80 7 30 20 8 15 320 9 10 10 10 90 120 11 30 70 12 5 10 13 50 10 14 50 100 15 20 10 16 5 5 17 75 15 18 45 110 19 50 50 20 50 105 21 20 35 22 20 35 23 20 35
Решение задачи: «Как работает классическая сборка мусора в лиспе? Сколько памяти занимает cons-ячейка?»
textual
Листинг программы
(defun powerset-2 (lst maxWeight) (let ((result nil) (temp nil) (b-val 0) (n-val 0)) (loop for i below (expt 2 (length lst)) do (setf temp (loop for j below i for x in lst if (logbitp j i) collect x) n-val (sum-by-param 'thing-value temp)) (if (<= (sum-by-param 'thing-weight temp) maxWeight) (cond ((= n-val b-val) (setf result (append result (list temp)))) ((> n-val b-val) (setf b-val n-val result (list temp)))))) (values result b-val (sum-by-param 'thing-weight (first result)))))
Объяснение кода листинга программы
В этом коде реализована функция powerset-2, которая вычисляет все возможные подмножества элементов списка lst с суммарным весом не больше maxWeight. В коде определены следующие переменные:
- result - результат работы функции, список всех подмножеств
- temp - временная переменная, используется для хранения промежуточных результатов
- b-val - текущий вес текущего подмножества
- n-val - текущее количество элементов текущего подмножества Код работает следующим образом:
- В цикле перебираются все возможные значения i от 0 до 2 в степени длины списка lst.
- Для каждого значения i создается новое подмножество элементов списка lst, которые имеют вес i.
- Если суммарный вес текущего подмножества не превышает maxWeight, то проверяется, является ли текущий вес равным предыдущему.
- Если текущий вес больше предыдущего, то обновляется значение предыдущего веса и добавляется текущее подмножество в результат.
- Возвращаются результат, текущий вес и суммарный вес всех элементов первого подмножества в результате. Для более подробного объяснения кода необходимо знать, что такое функция sum-by-param и что означают параметры 'thing-value и 'thing-weight.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д