Lisp 中的列表生成
List Generation in Lisp
为什么人们说 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 的幕后工作原理，但我需要生成一个包含很多列表的列表。有没有办法在不 运行ning 出堆 space 的情况下做到这一点？
谢谢
> Why do people say lists come for free in Lisp?
不知道。
看来您需要了解列表在内存中的存储方式。这使您能够计算出列表需要多少 space。
cons cell 由两个插槽组成。像 (a b c) 这样的列表存储为 (cons 'a (cons 'b (cons 'c '())))。一个简单的模型是将 cons cell 视为两个指针。 (cons 'a ...) 中的第一个指针指向符号。第二个指针指向下一个 cons 单元。因此，cons 单元使用两个 64 位字。对于小数字列表，数字可以直接存储在 cons 单元中，因此数字列表 (list 1 2 3) 使用 4 个 64 位字。
鉴于此，您应该能够计算出您的示例需要多少 space。
您遇到的问题是您试图创建 100*100*100*100*50 个列表，每个列表包含 5 个元素，即 50 亿个列表，总共有 250 亿个元素。长话短说，它不适合分配给 lisp 图像的内存量。即使您将整个内存分配给 lisp，它也可能不适合。
编辑：
让我们计算一些最佳情况下限。
acc 列表包含 50 亿个元素，即 50 亿个 cons 单元格。
32位计算机可以寻址的最大内存量是4GiB，所以32位是不可能的。 64 位计算机可以使用更多，但这也意味着我们的指针将是两倍长。
每个 cons cell 必须至少有 2 个 64 位（8 字节）指针。此外，每个 cons 单元必须有一些指示表明它是一个 cons 单元，垃圾收集器的标志，可能是空值的标志等。假设我们可以将它们压缩在一个字节中。因此，我们的 cons cells 之一可以放入 1 + 2 * 8 字节 = 17 字节的内存中。
50 亿 * 17 字节 = 850 亿字节 ~= 需要 79GiB 内存
这 50 亿个列表中的每一个都包含 5 个 cons 单元格:
250 亿 * 17 字节 = 4250 亿字节 ~= 需要 396GiB 内存
最后，这 250 亿个单元格中的每一个都包含一个整数。在您的情况下，这些是长整数，但是通过适当的声明，您可以在某些实现中将它们压缩为一个字节，再加上一个字节用于类型指示，除了最后一个 m 变量，它必须是两个字节+ 类型指示。因此每个列表的整数至少占
4*2 + 3 字节 = 每个列表 11 个字节用于存储整数。
50 亿个列表 * 11 字节 = 550 亿字节 ~= 需要 51GiB 内存
总共，这加起来至少 526GiB 内存 space 并且全部分配给 Lisp 解释器 - 只是为了存储您的数据，不包括 lisp 图像本身，OS，等等。它还需要优化的整数和优化的实现，可以在那些紧张的条件下做到这一点。
有解决办法：
- 购买几 TB 的 SSD
- 将其指定为交换
- ????
- 利润...
对于戒烟者或头脑清醒的人来说，有一种更便宜的解决方案：
http://en.wikipedia.org/wiki/Lazy_evaluation
为什么人们说 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 的幕后工作原理，但我需要生成一个包含很多列表的列表。有没有办法在不 运行ning 出堆 space 的情况下做到这一点？
谢谢
> Why do people say lists come for free in Lisp?
不知道。
看来您需要了解列表在内存中的存储方式。这使您能够计算出列表需要多少 space。
cons cell 由两个插槽组成。像 (a b c) 这样的列表存储为 (cons 'a (cons 'b (cons 'c '())))。一个简单的模型是将 cons cell 视为两个指针。 (cons 'a ...) 中的第一个指针指向符号。第二个指针指向下一个 cons 单元。因此，cons 单元使用两个 64 位字。对于小数字列表，数字可以直接存储在 cons 单元中，因此数字列表 (list 1 2 3) 使用 4 个 64 位字。
鉴于此，您应该能够计算出您的示例需要多少 space。
您遇到的问题是您试图创建 100*100*100*100*50 个列表，每个列表包含 5 个元素，即 50 亿个列表，总共有 250 亿个元素。长话短说，它不适合分配给 lisp 图像的内存量。即使您将整个内存分配给 lisp，它也可能不适合。
编辑：
让我们计算一些最佳情况下限。
acc 列表包含 50 亿个元素，即 50 亿个 cons 单元格。
32位计算机可以寻址的最大内存量是4GiB，所以32位是不可能的。 64 位计算机可以使用更多，但这也意味着我们的指针将是两倍长。
每个 cons cell 必须至少有 2 个 64 位（8 字节）指针。此外，每个 cons 单元必须有一些指示表明它是一个 cons 单元，垃圾收集器的标志，可能是空值的标志等。假设我们可以将它们压缩在一个字节中。因此，我们的 cons cells 之一可以放入 1 + 2 * 8 字节 = 17 字节的内存中。
50 亿 * 17 字节 = 850 亿字节 ~= 需要 79GiB 内存
这 50 亿个列表中的每一个都包含 5 个 cons 单元格:
250 亿 * 17 字节 = 4250 亿字节 ~= 需要 396GiB 内存
最后，这 250 亿个单元格中的每一个都包含一个整数。在您的情况下，这些是长整数，但是通过适当的声明，您可以在某些实现中将它们压缩为一个字节，再加上一个字节用于类型指示，除了最后一个 m 变量，它必须是两个字节+ 类型指示。因此每个列表的整数至少占
4*2 + 3 字节 = 每个列表 11 个字节用于存储整数。
50 亿个列表 * 11 字节 = 550 亿字节 ~= 需要 51GiB 内存
总共，这加起来至少 526GiB 内存 space 并且全部分配给 Lisp 解释器 - 只是为了存储您的数据，不包括 lisp 图像本身，OS，等等。它还需要优化的整数和优化的实现，可以在那些紧张的条件下做到这一点。
有解决办法：
- 购买几 TB 的 SSD
- 将其指定为交换
- ????
- 利润...
对于戒烟者或头脑清醒的人来说，有一种更便宜的解决方案：
http://en.wikipedia.org/wiki/Lazy_evaluation