Scheme中list是怎麼實現的？

01-30

在Racket里創建了一個5百萬元素的list，存放的都是隨機數。
通過list-ref訪問第0個元素和最後一個元素的速度看上去差不多，感覺list中的元素可以像數組一樣隨機訪問，效率很高。
本人初學，還沒達到分析源碼的水平。請高手答疑解惑：

list採用了什麼優化方案，可以高效地隨機訪問list中的元素？

list常用操作、以及在list首尾添加元素、鏈接兩個list等，效率怎麼樣？

提倡使用哪些list操作？應該盡量避免使用哪些list操作？

既然訪問list效率不差，vector存在的意義又是什麼？

要是list能隨機訪問，scheme標準里還要vector作甚？

其實隨機訪問和cons/car/cdr一個快了另一個就得慢下來，而且有Bootstrapping one-sided flexible arrays這種數據結構可以根據需求具體調節。。Okasaki的PFDS里就講了若干種random-access list的實現。。

但是。。Scheme是不會往標準裡面加這麼複雜的數據結構的。。開天闢地，唯cons/car/cdr足矣，pointer machine模型才是lisp，不，函數式語言的根基。。加入vector只是工程上的折衷。。

你確定不是只是「看上去」么？

======

別說 500W 了，我們就拿 N = 5K 和迭代次數 M = 10W 來測試，list-ref 訪問大「下標」比小「下標」都要慢很多

list 的原理就是用單鏈表實現的，確切地說實際上就是

list = null ;; ()

| { car : Any, cdr : Any }

proper-list 不過就是其 cdr 必須也是 list 罷了

而對於單鏈表，list-ref 的複雜度就很明顯了：是 O(index)，線性的

vector 就是數組實現 (array of Any)，隨機訪問 (vector-ref) 就沒這個問題

那麼對於其它的一些 list 操作，既然你明白了 list 的本質結構就是單鏈表，那麼相對應函數的複雜度就不難分析了

對於一些簡單的 benchmark，TZ 我教你一招，最簡單的

循環若干次做同樣的事，然後時間差立馬就被放大了，效率差距就變得明顯了

Lisp 里的 List 就是鏈表

struct cons {

lispObj* value;

cons* cdr;

};

這種感覺