Как работает классическая сборка мусора в лиспе? Сколько памяти занимает cons-ячейка? - Lisp

Узнай цену своей работы

Формулировка задачи:

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

Решение задачи: «Как работает классическая сборка мусора в лиспе? Сколько памяти занимает cons-ячейка?»

textual
Листинг программы
  1. (defun powerset-2 (lst maxWeight)
  2.   (let ((result nil)
  3.         (temp   nil)
  4.         (b-val    0)
  5.         (n-val    0))
  6.     (loop for i below (expt 2 (length lst)) do
  7.       (setf temp    (loop for j below i for x in lst if (logbitp j i) collect x)
  8.             n-val   (sum-by-param 'thing-value temp))
  9.       (if (<= (sum-by-param 'thing-weight temp) maxWeight)
  10.         (cond
  11.           ((= n-val b-val)
  12.             (setf result (append result (list temp))))
  13.           ((> n-val b-val)
  14.             (setf b-val     n-val
  15.                   result    (list temp))))))
  16.     (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

Нужна аналогичная работа?

Оформи быстрый заказ и узнай стоимость

Бесплатно
Оформите заказ и авторы начнут откликаться уже через 10 минут
Похожие ответы