Генерация списков в Lisp

Question

Почему люди говорят, что списки выходят бесплатно в Lisp?

Если я запускаю этот код

(let ((acc '())) 
     (do ((i 1 (incf i))) 
      ((= i 100)) 
     (do ((j 0 (incf j))) 
     ((= j 100)) 
      (do ((k 0 (incf k))) 
      ((= k 100)) 
     (do ((l 0 (incf l))) 
      ((= l 100)) 
      (do ((m 10 (+ 10 m))) 
       ((= m 500)) 
      (let ((unfiltered (copy-list '(0 0 0 0 0)))) 
       (setf (nth 0 unfiltered) i) 
       (setf (nth 1 unfiltered) j) 
       (setf (nth 2 unfiltered) k) 
       (setf (nth 3 unfiltered) l) 
       (setf (nth 4 unfiltered) m) 
       (push unfiltered acc)))))))) 

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

Благодаря

Answer 1

> Why do people say lists come for free in Lisp? 

Понятия не имею.

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

A cons cell состоит из двух слотов. Список, подобный (a b c), хранится как (cons 'a (cons 'b (cons 'c '()))). Простая модель - думать о ячейке cons как о двух указателях. Первый указатель в (cons 'a ...) указывает на символ. Второй указатель указывает на следующую ячейку cons cons. Таким образом, ячейка cons использует два 64-битных слова. Для списков небольших чисел номер может быть сохранен непосредственно в ячейке cons, поэтому список номеров (list 1 2 3) использует 4 64-битных слова.

Учитывая это, вы должны быть способны вычислить, сколько места вам нужен.

Answer 2

Проблема, с которой вы сталкиваетесь, заключается в том, что вы пытаетесь создать 100 * 100 * 100 * 100 * 50 списков по 5 элементов каждый, это 5 миллиардов списков с 25 миллиардами элементов. Короче говоря, он не вписывается в объем памяти, присвоенный lisp-изображению. Вероятно, он не поместится, даже если вы назначили всю свою память на lisp.

EDIT:
Давайте подсчитаем некоторые лучший случай нижних границ.

В списке acc содержится 5 миллиардов элементов, то есть 5 миллиардов cons cells.

Максимальный объем памяти 32-битного компьютера может равняться 4GiB, поэтому 32bit не может быть и речи. 64-битные компьютеры могут использовать гораздо больше, но это также означает, что наши указатели будут в два раза длиннее.

Каждый cons cell должен иметь не менее 2 64-битных (8 байт) указателей. Кроме того, каждая ячейка cons должна иметь некоторые признаки того, что это cons cell, флаги для сборщика мусора, возможно флаги для нулевых значений и т. Д. Давайте притворимся, что мы можем сжать их в один байт. Таким образом, один из наших cons ячеек может вписываться в 1 + 2 * 8 байтов = 17 байт памяти.

5 млрд * 17 байт = 85 миллиардов байт ~ = 79GiB требуемой памяти

Каждый из этих 5 миллиардов списков содержит 5 минусы клетки:

25 млрд * 17 байт = 425 млрд bytes ~ = Требуется 396GiB необходимой памяти

И, наконец, каждая из этих 25 миллиардов ячеек содержит одно целое число. Это длинные ints в вашем случае, но с соответствующим объявлением вы могли бы сжать их в один байт на некоторых реализациях плюс один байт для указания типа, за исключением последней переменной m, которая должна быть указана на два байта + типа. Поэтому целые числа каждого списка занимают не менее

4 * 2 + 3 байта = 11 байтов в списке для хранения целых чисел.

5000000000 списки * 11 байт = 55 миллиардов байт ~ = 51GiB памяти требуется

В общей сложности это составляет, по меньшей мере 526GiB пространства памяти и все назначенные на интерпретатор Лиспа - только для хранения ваши данные, не считая самого lisp-изображения, ОС и т. д. Он также требует оптимизированных целых чисел и оптимизированной реализации, которые могут сделать это в этих трудных условиях.

Там это решение:

1. Купить пару терабайт SSD-х
2. Назначают как своп
3. ????
4. Profit ...

И лодыри или здравомыслящих людей, есть один дешевый вариант:
http://en.wikipedia.org/wiki/Lazy_evaluation