4

Lisp 中的列表原语具有如下定义的运算符长度:

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

为什么某些 Lisp 的实现者不能将长度作为在恒定时间内计算的原语?

谢谢

4

4 回答 4

11

原因是 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”包含您希望列表包含的任何数据,例如数字,甚至链接到其他列表。“Rest”包含列表的其余部分。您实际上也可以将任何您想要的内容放入“rest”部分,但我们将在这里忽略它。)“Nil”是“空列表”,基本上表示“列表已结束!”

那么,如果我们想再次在前面加上一个“0”呢?

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

看?我们刚刚创建了一个指向旧列表开头的新 cons 单元格。你会听到人们把这称为“consing”一个价值放在前面。但是,您会注意到列表的其余部分未受影响。

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

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

如果您将“5”替换为“13”并分享更改会怎样?

[ 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]

是的。我们刚刚做了两个指向旧列表的 cons。列表的其余部分是共享的。而且,如果我们将 '5' 替换为 '13':

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

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

所有这一切的关键在于,与许多人所期望的不同,传统的 Lisp 列表并不是一个单一的东西。它们是一堆相互指向的小东西(conses)组成一个链,也就是列表。如果你想得到链条的长度,你必须遵循所有的小链接,直到你到达最后,nil。因此,O(n) 长度。

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


链表乐趣:

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

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

于 2011-06-21T07:28:48.850 回答
3

大多数 Lisp 方言没有将列表作为原始数据类型。例如,在 Common Lisp 中,列表由 cons 单元格和空列表(又名 NIL)组成。一个 cons 单元是一个具有两个字段的数据结构:CAR 和 CDR。使用 cons 单元格和 NIL 可以提供很多数据结构:单链表、关联表、循环表、树...

Lisp 可以以不同的方式实现列表(没有 conses),但通常它没有。

顺便说一句,Common Lisp 具有带填充指针的可调整数组。填充指针提供 O(1) 中的长度。

于 2011-06-20T23:20:37.173 回答
1

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

于 2011-06-20T20:50:33.770 回答
1

因为人们不会经常要求列表的长度来证明空间成本是合理的。如果你这样做了,你就做错了。

于 2011-06-20T20:53:09.417 回答