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? 

不知道。

看來你需要一個關於如何在內存中存儲列表的心理想法。這使您能夠計算列表需要多少空間。

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位字。

鑑於此，您應該能夠計算您的示例需要多少空間。

Answer 2

您遇到的問題是，您正在嘗試創建100 * 100 * 100 * 100 * 50的每個5個元素的列表，即總共有250億個元素的50億個列表。長話短說，它不適合分配給lisp映像的內存量。即使您將整個內存分配給lisp，它也可能不適合。

編輯：
讓我們來計算一些最好的情況下界。

acc列表包含50億個元素，即50億個個單元格。

32位計算機可以解決的最大內存容量是4GiB，所以32位是不成問題的。 64位計算機可以使用更多，但這也意味着我們的指針將會延長兩倍。

每個cons cell必須至少有2個64位（8字節）指針。此外，每個反應細胞必須有一些跡象表明它是一個反滲透細胞，垃圾收集器的標誌，空值等標誌。讓我們假裝我們可以在一個字節中擠壓這些標誌。我們的一個cons單元因此可以適合1 + 2 * 8字節= 17字節的存儲器。

5十億* 17個字節= 85十億字節〜=的存儲器79GiB需要

每個那些5所十億列出的含有5個缺點細胞：

25十億* 17個字節= 425十億字節〜= 需要內存396GiB

最後，這250億個單元中的每一個都包含一個整數。在你的情況下，這些都是長整數，但是如果聲明正確，你可以在一些實現中將它們壓縮成一個字節，再加上一個字節作爲類型指示，除了最後的m變量，必須是兩個字節+類型指示。因此，每個列表的整數至少佔用每個列表4 * 2 + 3個字節= 11個字節用於存儲整數。

5十億列表* 11個字節= 55個十億字節〜= 51GiB存儲器所需

總的來說，這個加起來至少526GiB的存儲器空間並都轉讓給Lisp解釋 - 只是存儲你的數據，不包括lisp鏡像本身，操作系統等。它還需要優化的整數和優化的實現，可以在這些嚴格的條件下完成。

有一個解決方案：固態硬盤的

TB的

1. 夫婦購買其指定爲交換
2. ????
3. 利潤...

併爲戒菸者或有理智的人，有一個便宜的解決方案：
http://en.wikipedia.org/wiki/Lazy_evaluation