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 回答