在Lisp和其他函数式语言中,为什么长度不是O(1)

Question

Lisp中的列表原语的opperator长度定义如下:

(define (length lst)
  (if (null? lst) 0 (+ 1 (length (cdr lst)))))

为什么一些Lisp的实现者不能使长度成为在恒定时间内计算的原语？

谢谢

Answer 1

原因是Lisp中列表的"传统"实现.在其他地方,列表有时与数组类似地实现.因此,当您创建列表时,它是一个单独的,自包含的东西.

An array-like list: [ 1 2 3 4 5 6 ]

如果你想将一个项目 - 例如'0'添加到该列表的开头(假设列表实现过于简单化),列表中的所有项目都将向上移动(向右).然后,'0'将安装在新的位置.

Step 0. [ 1 2 3 4 5 6 ]
Step 1. [   1 2 3 4 5 6 ] (Shift Right)
Step 2. [ 0 1 2 3 4 5 6 ] (Insert)

这不是(传统的)Lisp列表的方式.列表中的每个项目都是指向下一个项目的单独项目.列表的部分称为"conses".(这称为链表.)

[1] -> [2] -> [3] -> [4] -> [5] -> [6] -> nil

咦？那些,每个项目都是一个利弊细胞.每个cons单元都有两个值:car和cdr.(当cons单元与列表一起使用时,将"car"和"cdr"视为"first"和"rest"更好."First"保存您希望列表保存的任何数据,例如数字,甚至链接到其他列表."休息"占据了列表的其余部分.你实际上也可以将你想要的任何内容放入"休息"部分,但我们会在这里忽略它.)"Nil"是"空列表",基本上意思是"名单已经结束!"

那么,如果我们想再次在前面加上'0'怎么办？

[0] -> [1] -> [2] -> [3] -> [4] -> [5] -> [6] -> nil

看到？我们刚刚创建了一个新的cons单元,指向旧列表的开头.你会听到人们称之为"消耗"一个值在前面.但是,您会注意到列表的其余部分未受影响.

好的,但为什么有人想要这个呢？您可以共享列表.想象一下,你想要两个基本相同的列表.只是现在你想要一个列表以'7'开头,另一个列表以'4'开头？好吧,使用类似数组的方式,我们必须有两个列表.

[ 7 0 1 2 3 4 5 6 ]
[ 4 0 1 2 3 4 5 6 ]

如果你用'13'代替'5'并分享变化怎么办？

[ 7 0 1 2 3 4 13 6 ]
[ 4 0 1 2 3 4 5 6 ]

你有两个完全独立的列表.如果要共享更改,则必须在两个列表中进行更改.

传统的Lisp列表会发生什么？首先,在前面贴上'7'和'4':

[7]
   \
    ----> [0] -> [1] -> [2] -> [3] -> [4] -> [5] -> [6] -> nil
   /
[4]

对.我们刚刚提出两个指向旧列表的conses.列表的其余部分是共享的.而且,如果我们用'13'代替'5':

[7]
   \
    ----> [0] -> [1] -> [2] -> [3] -> [4] -> [13] -> [6] -> nil
   /
[4]

两个列表都会得到更改,因为其余列表是共享的.

所有这一切的重点在于,与许多人所期望的不同,传统的Lisp列表并不是单一的.它们是一堆小东西(conses),彼此指向形成一个链,这是列表.如果你想获得链条的长度,你必须遵循所有的小链接,直到你到达终点,零.因此,O(n)长度.

如果它们像数组一样完成,则可以将Lisp列表设为O(1).我确定一些不起眼的Lisps会这样做,并完全摆脱链表(conses).但是,conses似乎是进入基本上每种流行的Lisp方言的东西之一.如果你想要O(1)长度和查找,它们中的大多数也提供数组或向量.

链接列表的乐趣:

 -----------------<------------------------<----------
|                                                     |
 --> [0] -> [1] -> [2] -> [3] -> [4] -> [5] -> [6] -->

这个链表最终指向自己.如果你使用你的长度函数,它将永远循环,寻找结束,但永远不会找到它.

Answer 2

普通链表的复杂度为 O(n)，但还有其他可用的数据结构。例如，Clojure 实现了具有 O(1) 计数的List 和 Vector 。