Как работает классическая сборка мусора в лиспе? Сколько памяти занимает 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. В коде определены следующие переменные:

  1. result - результат работы функции, список всех подмножеств
  2. temp - временная переменная, используется для хранения промежуточных результатов
  3. b-val - текущий вес текущего подмножества
  4. n-val - текущее количество элементов текущего подмножества Код работает следующим образом:
  5. В цикле перебираются все возможные значения i от 0 до 2 в степени длины списка lst.
  6. Для каждого значения i создается новое подмножество элементов списка lst, которые имеют вес i.
  7. Если суммарный вес текущего подмножества не превышает maxWeight, то проверяется, является ли текущий вес равным предыдущему.
  8. Если текущий вес больше предыдущего, то обновляется значение предыдущего веса и добавляется текущее подмножество в результат.
  9. Возвращаются результат, текущий вес и суммарный вес всех элементов первого подмножества в результате. Для более подробного объяснения кода необходимо знать, что такое функция sum-by-param и что означают параметры 'thing-value и 'thing-weight.

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

5   голосов , оценка 3.2 из 5
Похожие ответы